[BOJ 3392] 화성 지도

https://www.acmicpc.net/problem/3392

3392번: 화성 지도

Tag : simd
스위핑하면서 (r-l)/16번 나이브하게 더해줬다. 
시복은 \(O(30000^2 / 16) \)

썸넬용사진

코드 

#pragma GCC optimize ("O3,unroll-loops")
#pragma GCC target ("avx,avx2,fma")
#include <bits/stdc++.h>
#include <immintrin.h>

using namespace std;


#define int short
const int X = 30000;
vector<pair<int, int>> in[X + 2], out[X + 2];
alignas(16) int cnt[X + 1];
alignas(16) int C[16];

signed main()
{
	cin.tie(0)->sync_with_stdio(0);
	int n; cin >> n;
	while(n--) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		in[x1].push_back({y1, y2 - 1});
		out[x2].push_back({y1, y2 - 1});
	}
	signed ans = 0;
	__m256i BASE = _mm256_set1_epi16(1);
	__m256i ZERO = _mm256_setzero_si256();
	for(int i = 0; i <= X; i++) {
		for(auto &[l, r] : in[i]) {
			while(l & 15 and l <= r) cnt[l++]++;
			int j;
			for(j = l; j + 15 <= r; j += 16) {
				__m256i t = _mm256_load_si256((__m256i*)(cnt + j));
				__m256i tt = _mm256_add_epi16(t, BASE);
				_mm256_store_si256((__m256i*)(cnt + j), tt);
			}
			while(j <= r) cnt[j++]++;
		}
		for(auto &[l, r] : out[i]) {
			while(l & 15 and l <= r) cnt[l++]--;
			int j;
			for(j = l; j + 15 <= r; j += 16) {
				__m256i t = _mm256_load_si256((__m256i*)(cnt + j));
				__m256i tt = _mm256_sub_epi16(t, BASE);
				_mm256_store_si256((__m256i*)(cnt + j), tt);
			}
			while(j <= r) cnt[j++]--;
		}
		int l = 0;
		__m256i res = _mm256_setzero_si256();
        	for (; l + 15 <= X; l += 16) {
            	__m256i t = _mm256_load_si256((__m256i*)(cnt + l));
            	res = _mm256_add_epi16(res, _mm256_and_si256(_mm256_cmpgt_epi16(t, ZERO), BASE));
        	}
		while(l <= X) ans += cnt[l++] > 0;
		_mm256_store_si256((__m256i*)C, res);
		for(int j = 0; j < 16; j++) ans += C[j];
	}
	cout << ans << '\n';
}