結果
問題 | No.961 Vibrant Fillumination |
ユーザー |
![]() |
提出日時 | 2019-12-24 01:46:22 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,779 ms / 5,000 ms |
コード長 | 3,861 bytes |
コンパイル時間 | 1,557 ms |
コンパイル使用メモリ | 128,332 KB |
実行使用メモリ | 149,340 KB |
最終ジャッジ日時 | 2024-09-22 16:55:23 |
合計ジャッジ時間 | 22,712 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 48 |
ソースコード
#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 vector<T> bit; int size; BIT(int n):size(n), bit(n+1, 0){} T sum(int i){ T s=0; while(i>0){ s+=bit[i]; i-=(i&(-i)); } return s; } void add(int i, T x){ while(i<=size){ bit[i]+=x; i+=(i&(-i)); } } }; template<typename T> struct BITxor{ //1-indexed vector<T> bit; int size; BITxor(int n):size(n), bit(n+1, 0){} T sum(int i){ T s=0; while(i>0){ s^=bit[i]; i-=(i&(-i)); } return s; } void add(int i, T x){ while(i<=size){ 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]; //vector<int> vl[100010], vr[100010]; ll ans[50050]; int q[50050]; vector<int> vq[100010]; void calc(int e){ if(ind[e].empty()) return; BIT<int> bit(2*n); vector<int> vl3[100010], vr3[100010]; for(auto k:ind[e]){ vl3[a[k]].push_back(k); vr3[c[k]].push_back(k); } for(int i=0; i<2*n; i++){ for(auto k:vl3[i]){ bit.add(b[k]+1, 1); bit.add(d[k]+1, -1); } for(auto k:vr3[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]; } } } } int sum[110][110]; vector<Pl> vl2[100010], vr2[100010]; void calc2(int e){ vector<int> vx, vy; for(auto k:ind[e]){ vx.push_back(a[k]); vx.push_back(c[k]); vy.push_back(b[k]); vy.push_back(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(){ BITxor<ll> bit(2*n); 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++) cin>>h[i]; for(int i=0; i<n; i++){ cin>>a[i]>>b[i]>>c[i]>>d[i]>>e[i]; e[i]--; ind[e[i]].push_back(i); //vl[a[i]].push_back(i); //vr[c[i]].push_back(i); } cin>>Q; for(int i=0; i<Q; i++){ int pi; cin>>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; }