#411601 (C++14) No.961 Vibrant Fillumination

提出ソース

結果

問題	No.961 Vibrant Fillumination
ユーザー	FF256grhy
提出日時	2019-12-24 02:49:06
言語	C++14 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	1,734 ms / 5,000 ms
コード長	3,717 bytes
コンパイル時間	2,601 ms
コンパイル使用メモリ	192,268 KB
実行使用メモリ	22,672 KB
最終ジャッジ日時	2023-10-24 00:00:24
合計ジャッジ時間	63,583 ms
ジャッジサーバーID （参考情報）	judge12 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,348 KB
testcase_01	AC	2 ms 4,348 KB
testcase_02	AC	942 ms 22,408 KB
testcase_03	AC	1,237 ms 22,468 KB
testcase_04	AC	1,484 ms 22,408 KB
testcase_05	AC	1,421 ms 22,408 KB
testcase_06	AC	1,075 ms 22,420 KB
testcase_07	AC	1,100 ms 22,408 KB
testcase_08	AC	1,091 ms 22,408 KB
testcase_09	AC	1,245 ms 22,408 KB
testcase_10	AC	1,501 ms 22,464 KB
testcase_11	AC	1,416 ms 22,476 KB
testcase_12	AC	1,374 ms 22,476 KB
testcase_13	AC	1,466 ms 22,476 KB
testcase_14	AC	1,702 ms 22,672 KB
testcase_15	AC	1,556 ms 22,476 KB
testcase_16	AC	1,734 ms 22,468 KB
testcase_17	AC	1,631 ms 22,448 KB
testcase_18	AC	1,670 ms 22,464 KB
testcase_19	AC	1,617 ms 22,472 KB
testcase_20	AC	1,564 ms 22,456 KB
testcase_21	AC	1,554 ms 22,464 KB
testcase_22	AC	1,442 ms 22,456 KB
testcase_23	AC	1,287 ms 22,472 KB
testcase_24	AC	1,279 ms 22,672 KB
testcase_25	AC	1,319 ms 22,460 KB
testcase_26	AC	741 ms 22,464 KB
testcase_27	AC	687 ms 22,416 KB
testcase_28	AC	856 ms 22,464 KB
testcase_29	AC	769 ms 22,408 KB
testcase_30	AC	204 ms 19,768 KB
testcase_31	AC	325 ms 19,892 KB
testcase_32	AC	158 ms 19,192 KB
testcase_33	AC	2 ms 4,348 KB
testcase_34	AC	1,097 ms 22,464 KB
testcase_35	AC	1,072 ms 22,476 KB
testcase_36	AC	1,123 ms 22,476 KB
testcase_37	AC	1,068 ms 22,476 KB
testcase_38	AC	1,153 ms 22,672 KB
testcase_39	AC	979 ms 22,476 KB
testcase_40	AC	1,085 ms 22,468 KB
testcase_41	AC	1,065 ms 22,448 KB
testcase_42	AC	1,080 ms 22,464 KB
testcase_43	AC	1,092 ms 22,472 KB
testcase_44	AC	1,146 ms 22,456 KB
testcase_45	AC	1,485 ms 22,464 KB
testcase_46	AC	1,151 ms 22,456 KB
testcase_47	AC	895 ms 22,472 KB
testcase_48	AC	969 ms 22,672 KB
testcase_49	AC	1,609 ms 22,460 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード