Submission #644683

#	Time	Username	Problem	Language	Result	Execution time	Memory
644683		ymm	운세 보기 2 (JOI14_fortune_telling2)	C++17	0 / 100	1 ms	340 KiB

fortune_telling2

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 200'032;
const int S0 = 32767;
const int S1 = 2048;
int a[N], b[N];
short sa[N], sb[N];
int q[N];
short sq[N];
int n;

__attribute__((optimize("O3,unroll-loops"),target("avx2")))
void up(short x, short y, short z, int l, int r)
{
	Loop (i,l,r) {
		short v = sa[i], u = sb[i];
		v ^= v <= x? u: 0;
		v ^= v <= y? u: 0;
		v ^= v <= z? u: 0;
		sa[i] = v;
	}
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int k;
	cin >> n >> k;
	Loop (i,0,n)
		cin >> a[i] >> b[i];
	Loop (i,0,k)
		cin >> q[i];
	ll ans = 0;
	for (int l0 = 0; l0 < n; l0 += S0) {
		int r0 = min(n, l0+S0);
		vector<int> vec = {0};
		Loop (i,l0,r0) {
			vec.push_back(a[i]);
			vec.push_back(b[i]);
		}
		sort(vec.begin(), vec.end());
		vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
		Loop (i,l0,r0) {
			sa[i] = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin();
			sb[i] = lower_bound(vec.begin(), vec.end(), b[i]) - vec.begin();
			sb[i] ^= sa[i];
		}
		Loop (i,0,k)
			sq[i] = upper_bound(vec.begin(), vec.end(), q[i]) - vec.begin() - 1;
		for (int l1 = l0; l1 < r0; l1 += S1) {
			int r1 = min(r0, l1+S1);
			for (int i = 0; i < k; i += 3)
				up(q[i+0], q[i+1], q[i+2], l1, r1);
		}
		Loop (i,l0,r0)
			ans += vec[sa[i]];
	}
	cout << ans << '\n';
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 31
• Subtask 3: 0 / 65