#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include #include #include using namespace std; // Using aligned_alloc for C++11/17 compatibility long long* allocate_aligned(size_t n) { // 32-byte alignment for AVX2 void* ptr = nullptr; if (posix_memalign(&ptr, 32, n * sizeof(long long)) != 0) return nullptr; return (long long*)ptr; } int main() { // Fast I/O is crucial for 10^5 queries ios::sync_with_stdio(false); cin.tie(NULL); int N; if (!(cin >> N)) return 0; // Allocate N+1 to handle 1-based indexing safely long long* arr = allocate_aligned(N + 4); for (int i = 1; i <= N; ++i) { cin >> arr[i]; } int Q; cin >> Q; while (Q--) { int type; cin >> type; if (type == 1) { int pos; long long val; cin >> pos >> val; arr[pos] = val; } else { int l, r; cin >> l >> r; long long total_sum = 0; int i = l; // Initialize a 256-bit vector of zeros (holds 4 x 64-bit integers) __m256i vsum = _mm256_setzero_si256(); // Main SIMD loop: process 4 elements at a time for (; i + 3 <= r; i += 4) { // loadu (unaligned load) is safer for arbitrary l/r ranges __m256i vdata = _mm256_loadu_si256((__m256i*)&arr[i]); vsum = _mm256_add_epi64(vsum, vdata); } // Extract the 4 partial sums from the vector alignas(32) long long temp[4]; _mm256_store_si256((__m256i*)temp, vsum); total_sum = temp[0] + temp[1] + temp[2] + temp[3]; // Clean up remainder elements while (i <= r) { total_sum += arr[i++]; } cout << total_sum << "\n"; } } free(arr); return 0; }

Submission #99

Source Code