Submission #155244

#TimeUsernameProblemLanguageResultExecution timeMemory
155244arnold518Land of the Rainbow Gold (APIO17_rainbow)C++14
0 / 100
319 ms139700 KiB
#include "rainbow.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 2e5; struct SEG { vector<int> tree[MAXN*4+10]; void push(int node, int tl, int tr, int pos, int val) { if(tl==tr) { tree[node].push_back(val); return; } int mid=tl+tr>>1; if(pos<=mid) push(node*2, tl, mid, pos, val); else push(node*2+1, mid+1, tr, pos, val); } void init(int node, int tl, int tr) { if(tl==tr) { sort(tree[node].begin(), tree[node].end()); return; } int mid=tl+tr>>1; init(node*2, tl, mid); init(node*2+1, mid+1, tr); tree[node].resize(tree[node*2].size()+tree[node*2+1].size()); merge(tree[node*2].begin(), tree[node*2].end(), tree[node*2+1].begin(), tree[node*2+1].end(), tree[node].begin()); } int query(int node, int tl, int tr, int xl, int xr, int yl, int yr) { if(xl>xr || yl>yr) return 0; if(xr<tl || tr<xl) return 0; if(xl<=tl && tr<=xr) return upper_bound(tree[node].begin(), tree[node].end(), yr)-lower_bound(tree[node].begin(), tree[node].end(), yl); int mid=tl+tr>>1; return query(node*2, tl, mid, xl, xr, yl, yr)+query(node*2+1, mid+1, tr, xl, xr, yl, yr); } }; SEG segv, sege1, sege2, segf; int R, C; void init(int _R, int _C, int sy, int sx, int M, char *S) { int i, j; R=_R; C=_C; vector<pii> T, TT; T.push_back({sx, sy}); T.push_back({sx, sy-1}); T.push_back({sx-1, sy}); T.push_back({sx-1, sy-1}); TT.push_back({sx, sy}); for(i=0; i<M; i++) { if(S[i]=='N') sy--; if(S[i]=='W') sx--; if(S[i]=='S') sy++; if(S[i]=='E') sx++; T.push_back({sx, sy}); if(sy-1>0) T.push_back({sx, sy-1}); if(sx-1>0) T.push_back({sx-1, sy}); if(sx-1>0 && sy-1>0) T.push_back({sx-1, sy-1}); TT.push_back({sx, sy}); } sort(T.begin(), T.end()); T.erase(unique(T.begin(), T.end()), T.end()); sort(TT.begin(), TT.end()); TT.erase(unique(TT.begin(), TT.end()), TT.end()); for(auto it : TT) segv.push(1, 1, C, it.first, it.second); for(auto it : T) if(binary_search(TT.begin(), TT.end(), pii(it.first, it.second)) || binary_search(TT.begin(), TT.end(), pii(it.first, it.second+1))) sege1.push(1, 1, C, it.first, it.second); for(auto it : T) if(binary_search(TT.begin(), TT.end(), pii(it.first, it.second)) || binary_search(TT.begin(), TT.end(), pii(it.first+1, it.second))) sege2.push(1, 1, C, it.first, it.second); for(auto it : T) if(binary_search(TT.begin(), TT.end(), pii(it.first, it.second)) || binary_search(TT.begin(), TT.end(), pii(it.first+1, it.second)) || binary_search(TT.begin(), TT.end(), pii(it.first, it.second+1)) || binary_search(TT.begin(), TT.end(), pii(it.first+1, it.second+1))) segf.push(1, 1, C, it.first, it.second); segv.init(1, 1, C); sege1.init(1, 1, C); sege2.init(1, 1, C); segf.init(1, 1, C); } int colour(int Y1, int X1, int Y2, int X2) { ll v, e1, e2, f; v=(ll)(Y2-Y1+1)*(X2-X1+1)-segv.query(1, 1, C, X1, X2, Y1, Y2); e1=(ll)(Y2-Y1)*(X2-X1+1)-sege1.query(1, 1, C, X1, X2, Y1, Y2-1); e2=(ll)(Y2-Y1+1)*(X2-X1)-sege2.query(1, 1, C, X1, X2-1, Y1, Y2); f=(ll)(Y2-Y1)*(X2-X1)-segf.query(1, 1, C, X1, X2-1, Y1, Y2-1); //printf("%lld %lld %lld %lld\n", v, e1, e2, f); //printf("============================================\n"); return v-e1-e2+f; }

Compilation message (stderr)

rainbow.cpp: In member function 'void SEG::push(int, int, int, int, int)':
rainbow.cpp:18:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
rainbow.cpp: In member function 'void SEG::init(int, int, int)':
rainbow.cpp:30:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
rainbow.cpp: In member function 'int SEG::query(int, int, int, int, int, int, int)':
rainbow.cpp:42:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:52:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...