結果

問題 No.961 Vibrant Fillumination
コンテスト
ユーザー FF256grhy
提出日時 2019-12-24 02:49:06
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,197 ms / 5,000 ms
コード長 3,717 bytes
コンパイル時間 2,291 ms
コンパイル使用メモリ 191,620 KB
実行使用メモリ 22,528 KB
最終ジャッジ日時 2024-09-22 17:07:01
合計ジャッジ時間 48,218 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using LL = long long int;
#define incID(i, l, r) for(int i = (l)    ; i <  (r); ++i)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); ++i)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); --i)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); --i)
#define inc(i, n)  incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec(i, n)  decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))
#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
auto setmin   = [](auto & a, auto b) { return (b <  a ? a = b, true : false); };
auto setmax   = [](auto & a, auto b) { return (b >  a ? a = b, true : false); };
auto setmineq = [](auto & a, auto b) { return (b <= a ? a = b, true : false); };
auto setmaxeq = [](auto & a, auto b) { return (b >= a ? a = b, true : false); };
auto fl = [](auto a, auto b) { assert(b != 0); return a / b - (a % b != 0 && ((a >= 0) != (b >= 0)) ? 1 : 0); };
auto ce = [](auto a, auto b) { assert(b != 0); return a / b + (a % b != 0 && ((a >= 0) == (b >= 0)) ? 1 : 0); };
auto mo = [](auto a, auto b) { assert(b != 0); a %= b; if(a < 0) { a += abs(b); } return a; };
LL gcd(LL a, LL b) { return (b == 0 ? a : gcd(b, a % b)); }
LL lcm(LL a, LL b) { return a / gcd(a, b) * b; }
#define bit(b, i) (((b) >> (i)) & 1)
#define SI(v) static_cast<int>(v.size())
#define RF(e, v) for(auto & e: v)
#define until(e) while(! (e))
#define if_not(e) if(! (e))
#define ef else if
#define UR assert(false)

// ---- ----

#define LB(v, x) (lower_bound(ALL(v), x) - v.begin())
#define UB(v, x) (upper_bound(ALL(v), x) - v.begin())

const int M = 300;

int main() {
	int n;
	cin >> n;
	vector<LL> h(n);
	inc(i, n) { cin >> h[i]; }
	vector<int> a(n), b(n), c(n), d(n), e(n);
	inc(i, n) { cin >> a[i] >> b[i] >> c[i] >> d[i] >> e[i]; e[i]--; }
	int Q;
	cin >> Q;
	vector<pair<int, int>> p(Q);
	inc(i, Q) { cin >> p[i].FI >> p[i].SE; }
	
	int H = 2 * n;
	int W = 2 * n;
	vector<vector<int>> A(H), B(H), C(W), D(W);
	inc(i, n) {
		A[a[i]].PB(i);
		B[b[i]].PB(i);
		C[c[i]].PB(i);
		D[d[i]].PB(i);
	}
	
	vector<int> cut = { 0, W };
	inc(j, W) { if(SI(B[j]) + SI(D[j]) > M) { cut.PB(j); } }
	sort(ALL(cut));
	vector<int> cut2;
	inc(k, SI(cut) - 1) {
		int len = cut[k + 1] - cut[k];
		if(len > M) { inc1(l, len / M) { cut2.PB(cut[k] + l * M); } }
	}
	RF(e, cut2) { cut.PB(e); }
	sort(ALL(cut));
	
	const int BN = SI(cut) - 1;
	vector<vector<pair<pair<int, int>, int>>> P(BN);
	inc(k, Q) {
		int l = UB(cut, p[k].SE) - 1;
		P[l].EB(p[k], k);
	}
	inc(k, BN) { sort(ALL(P[k])); }
	
	vector<LL> ans(Q);
	inc(k, BN) {
		vector<int> v(n, 0);
		LL hash = 0;
		
		auto add = [&](int col) { if(v[col]++ == 0) { hash ^= h[col]; } };
		auto del = [&](int col) { if(--v[col] == 0) { hash ^= h[col]; } };
		
		auto R_ = [&](int i, int j) {
			RF(k, A[i]) { if(inID(j, b[k], d[k])) { add(e[k]); } }
			RF(k, C[i]) { if(inID(j, b[k], d[k])) { del(e[k]); } }
		};
		auto U_ = [&](int i, int j) {
			RF(k, B[j]) { if(inID(i, a[k], c[k])) { add(e[k]); } }
			RF(k, D[j]) { if(inID(i, a[k], c[k])) { del(e[k]); } }
		};
		auto D_ = [&](int i, int j) {
			RF(k, B[j]) { if(inID(i, a[k], c[k])) { del(e[k]); } }
			RF(k, D[j]) { if(inID(i, a[k], c[k])) { add(e[k]); } }
		};
		
		int i = -1, j = cut[k], PC = 0;
		while(PC < SI(P[k])) {
			while(i < P[k][PC].FI.FI) { R_(++i, j); }
			while(j < P[k][PC].FI.SE) { U_(i, ++j); }
			while(j > P[k][PC].FI.SE) { D_(i, j--); }
			ans[P[k][PC].SE] = hash;
			PC++;
		}
	}
	
	RF(e, ans) { cout << e << "\n"; }
	
	return 0;
}
0