結果
問題 | No.961 Vibrant Fillumination |
ユーザー | chocorusk |
提出日時 | 2019-12-24 01:57:39 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2,175 ms / 5,000 ms |
コード長 | 3,632 bytes |
コンパイル時間 | 3,519 ms |
コンパイル使用メモリ | 129,344 KB |
実行使用メモリ | 151,656 KB |
最終ジャッジ日時 | 2023-10-24 00:03:13 |
合計ジャッジ時間 | 21,305 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 7 ms
18,848 KB |
testcase_01 | AC | 6 ms
18,848 KB |
testcase_02 | AC | 232 ms
24,020 KB |
testcase_03 | AC | 236 ms
24,228 KB |
testcase_04 | AC | 227 ms
24,012 KB |
testcase_05 | AC | 228 ms
24,028 KB |
testcase_06 | AC | 225 ms
24,024 KB |
testcase_07 | AC | 224 ms
24,020 KB |
testcase_08 | AC | 224 ms
24,016 KB |
testcase_09 | AC | 224 ms
24,036 KB |
testcase_10 | AC | 148 ms
28,340 KB |
testcase_11 | AC | 152 ms
28,672 KB |
testcase_12 | AC | 143 ms
28,416 KB |
testcase_13 | AC | 146 ms
28,256 KB |
testcase_14 | AC | 150 ms
29,548 KB |
testcase_15 | AC | 140 ms
27,596 KB |
testcase_16 | AC | 148 ms
29,576 KB |
testcase_17 | AC | 140 ms
27,816 KB |
testcase_18 | AC | 144 ms
28,536 KB |
testcase_19 | AC | 143 ms
28,184 KB |
testcase_20 | AC | 144 ms
28,420 KB |
testcase_21 | AC | 147 ms
27,920 KB |
testcase_22 | AC | 145 ms
27,804 KB |
testcase_23 | AC | 139 ms
27,416 KB |
testcase_24 | AC | 148 ms
28,304 KB |
testcase_25 | AC | 153 ms
28,676 KB |
testcase_26 | AC | 94 ms
24,184 KB |
testcase_27 | AC | 117 ms
28,052 KB |
testcase_28 | AC | 111 ms
24,192 KB |
testcase_29 | AC | 120 ms
28,316 KB |
testcase_30 | AC | 95 ms
24,136 KB |
testcase_31 | AC | 80 ms
22,992 KB |
testcase_32 | AC | 108 ms
25,412 KB |
testcase_33 | AC | 7 ms
18,848 KB |
testcase_34 | AC | 2,175 ms
151,656 KB |
testcase_35 | AC | 1,546 ms
24,544 KB |
testcase_36 | AC | 1,043 ms
24,384 KB |
testcase_37 | AC | 813 ms
24,292 KB |
testcase_38 | AC | 665 ms
24,248 KB |
testcase_39 | AC | 569 ms
24,296 KB |
testcase_40 | AC | 499 ms
24,624 KB |
testcase_41 | AC | 451 ms
24,684 KB |
testcase_42 | AC | 381 ms
24,612 KB |
testcase_43 | AC | 354 ms
24,340 KB |
testcase_44 | AC | 335 ms
24,620 KB |
testcase_45 | AC | 327 ms
24,424 KB |
testcase_46 | AC | 297 ms
24,692 KB |
testcase_47 | AC | 286 ms
24,368 KB |
testcase_48 | AC | 268 ms
24,488 KB |
testcase_49 | AC | 262 ms
24,468 KB |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair<int, int> P; typedef pair<P, ll> Pl; template<typename T> struct BIT{ //1-indexed using F=function<T(T, T)>; const F f; vector<T> bit; int size; BIT(int n, const F f):f(f), size(n), bit(n+1, 0){} T sum(int i){ T s=0; while(i>0){ s=f(s, bit[i]); i-=(i&(-i)); } return s; } void add(int i, T x){ while(i<=size){ bit[i]=f(bit[i], x); i+=(i&(-i)); } } }; int n, Q; ll h[50050]; vector<int> ind[50050]; int a[50050], b[50050], c[50050], d[50050], e[50050]; ll ans[50050]; int q[50050]; vector<int> vq[100010]; vector<int> vl[100010], vr[100010]; void calc(int e){ BIT<int> bit(2*n, [](int a, int b){ return a+b;}); for(auto k:ind[e]){ vl[a[k]].push_back(k); vr[c[k]].push_back(k); } for(int i=0; i<2*n; i++){ for(auto k:vl[i]){ bit.add(b[k]+1, 1); bit.add(d[k]+1, -1); } for(auto k:vr[i]){ bit.add(b[k]+1, -1); bit.add(d[k]+1, 1); } for(auto k:vq[i]){ if(bit.sum(q[k]+1)>0) ans[k]^=h[e]; } vl[i].clear(); vr[i].clear(); } } int sum[110][110]; vector<Pl> vl2[100010], vr2[100010]; void calc2(int e){ if(ind[e].empty()) return; vector<int> vx(2*ind[e].size()), vy(2*ind[e].size()); int j=0; for(int j=0; j<ind[e].size(); j++){ int k=ind[e][j]; vx[2*j]=a[k], vx[2*j+1]=c[k], vy[2*j]=b[k], vy[2*j+1]=d[k]; } sort(vx.begin(), vx.end()); vx.erase(unique(vx.begin(), vx.end()), vx.end()); sort(vy.begin(), vy.end()); vy.erase(unique(vy.begin(), vy.end()), vy.end()); int nx=vx.size(), ny=vy.size(); for(int i=0; i<nx; i++) fill(sum[i], sum[i]+ny, 0); for(auto k:ind[e]){ int a1=lower_bound(vx.begin(), vx.end(), a[k])-vx.begin(); int b1=lower_bound(vy.begin(), vy.end(), b[k])-vy.begin(); int c1=lower_bound(vx.begin(), vx.end(), c[k])-vx.begin(); int d1=lower_bound(vy.begin(), vy.end(), d[k])-vy.begin(); sum[a1][b1]++; sum[a1][d1]--; sum[c1][b1]--; sum[c1][d1]++; } for(int i=0; i<nx; i++) for(int j=1; j<ny; j++) sum[i][j]+=sum[i][j-1]; for(int i=1; i<nx; i++) for(int j=0; j<ny; j++) sum[i][j]+=sum[i-1][j]; for(int i=0; i<nx-1; i++){ for(int j=0; j<ny-1; j++){ if(sum[i][j]>0){ vl2[vx[i]].push_back({{vy[j], vy[j+1]}, h[e]}); vr2[vx[i+1]].push_back({{vy[j], vy[j+1]}, h[e]}); } } } } void calc3(){ BIT<ll> bit(2*n, [](ll x, ll y){ return (x^y);}); for(int i=0; i<2*n; i++){ for(auto p:vl2[i]){ bit.add(p.first.first+1, p.second); bit.add(p.first.second+1, p.second); } for(auto p:vr2[i]){ bit.add(p.first.first+1, p.second); bit.add(p.first.second+1, p.second); } for(auto k:vq[i]){ ans[k]^=bit.sum(q[k]+1); } } } int main() { cin>>n; for(int i=0; i<n; i++) scanf("%lld", &h[i]); for(int i=0; i<n; i++){ scanf("%d %d %d %d %d", &a[i], &b[i], &c[i], &d[i], &e[i]); e[i]--; ind[e[i]].push_back(i); } cin>>Q; for(int i=0; i<Q; i++){ int pi; scanf("%d %d", &pi, &q[i]); vq[pi].push_back(i); } for(int i=0; i<n; i++){ if(ind[i].size()>=50) calc(i); else calc2(i); } calc3(); for(int i=0; i<Q; i++){ printf("%lld\n", ans[i]); } return 0; }