Submission #59643

#TimeUsernameProblemLanguageResultExecution timeMemory
59643dualityLand of the Rainbow Gold (APIO17_rainbow)C++11
47 / 100
3070 ms531432 KiB
#define DEBUG 0 #include <bits/stdc++.h> using namespace std; #if DEBUG // basic debugging macros int __i__,__j__; #define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl #define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl #define printVar(n) cout<<#n<<": "<<n<<endl #define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl #define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;} #define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;} // advanced debugging class // debug 1,2,'A',"test"; class _Debug { public: template<typename T> _Debug& operator,(T val) { cout << val << endl; return *this; } }; #define debug _Debug(), #else #define printLine(l) #define printLine2(l,c) #define printVar(n) #define printArr(a,l) #define print2dArr(a,r,c) #define print2dArr2(a,r,c,l) #define debug #endif // define #define MAX_VAL 999999999 #define MAX_VAL_2 999999999999999999LL #define EPS 1e-6 #define mp make_pair #define pb push_back // typedef typedef unsigned int UI; typedef long long int LLI; typedef unsigned long long int ULLI; typedef unsigned short int US; typedef pair<int,int> pii; typedef pair<LLI,LLI> plli; typedef vector<int> vi; typedef vector<LLI> vlli; typedef vector<pii> vpii; typedef vector<plli> vplli; // ---------- END OF TEMPLATE ---------- #include "rainbow.h" int r,c; int lx,rx,ly,ry; struct xNode { xNode *l,*r; int sum; xNode() { l = r = NULL; sum = 0; } int query(int s,int e,int qs,int qe) { if (s > e) return 0; else if ((s > qe) || (e < qs)) return 0; else if ((s >= qs) && (e <= qe)) return sum; int mid = (s+e) / 2; return ((l == NULL) ? 0:l->query(s,mid,qs,qe))+((r == NULL) ? 0:r->query(mid+1,e,qs,qe)); } int update(int s,int e,int ai) { if (s == e) { sum++; return sum; } int mid = (s+e) / 2; if (ai <= mid) { if (l == NULL) l = new xNode; sum = l->update(s,mid,ai)+((r == NULL) ? 0:r->sum); } else { if (r == NULL) r = new xNode; sum = r->update(mid+1,e,ai)+((l == NULL) ? 0:l->sum); } return sum; } }; struct yNode { yNode *l,*r; xNode *x; yNode() { l = r = NULL; x = new xNode; }; int query(int sy,int ey,int qys,int qye,int qxs,int qxe) { if (sy > ey) return 0; else if ((sy > qye) || (ey < qys)) return 0; else if ((sy >= qys) && (ey <= qye)) return x->query(0,c,qxs,qxe); int mid = (sy+ey) / 2; return ((l == NULL) ? 0:l->query(sy,mid,qys,qye,qxs,qxe))+((r == NULL) ? 0:r->query(mid+1,ey,qys,qye,qxs,qxe)); } int update(int sy,int ey,int ay,int ax) { if (sy == ey) { x->update(0,c,ax); return 0; } int mid = (sy+ey) / 2; if (ay <= mid) { if (l == NULL) l = new yNode; l->update(sy,mid,ay,ax); } else { if (r == NULL) r = new yNode; r->update(mid+1,ey,ay,ax); } x->update(0,c,ax); return 0; } }; vpii p1,p2,p3,p4; yNode *tree1,*tree2,*tree3,*tree4; void init(int R,int C,int sr,int sc,int M,char *S) { int i; r = R,c = C; tree1 = new yNode; tree2 = new yNode; tree3 = new yNode; tree4 = new yNode; sr--,sc--; lx = rx = sc,ly = ry = sr; p1.pb(mp(sr+1,sc+1)); p2.pb(mp(sr+1,sc+1)),p2.pb(mp(sr,sc+1)); p3.pb(mp(sr+1,sc+1)),p3.pb(mp(sr+1,sc)); p4.pb(mp(sr+1,sc+1)),p4.pb(mp(sr,sc+1)),p4.pb(mp(sr+1,sc)),p4.pb(mp(sr,sc)); for (i = 0; i < M; i++) { if (S[i] == 'N') sr--; else if (S[i] == 'S') sr++; else if (S[i] == 'W') sc--; else sc++; lx = min(lx,sc),rx = max(rx,sc); ly = min(lx,sr),ry = max(ry,sr); p1.pb(mp(sr+1,sc+1)); p2.pb(mp(sr+1,sc+1)),p2.pb(mp(sr,sc+1)); p3.pb(mp(sr+1,sc+1)),p3.pb(mp(sr+1,sc)); p4.pb(mp(sr+1,sc+1)),p4.pb(mp(sr,sc+1)),p4.pb(mp(sr+1,sc)),p4.pb(mp(sr,sc)); } sort(p1.begin(),p1.end()); p1.resize(unique(p1.begin(),p1.end())-p1.begin()); sort(p2.begin(),p2.end()); p2.resize(unique(p2.begin(),p2.end())-p2.begin()); sort(p3.begin(),p3.end()); p3.resize(unique(p3.begin(),p3.end())-p3.begin()); sort(p4.begin(),p4.end()); p4.resize(unique(p4.begin(),p4.end())-p4.begin()); for (i = 0; i < p1.size(); i++) tree1->update(0,r,p1[i].first,p1[i].second); for (i = 0; i < p2.size(); i++) tree2->update(0,r,p2[i].first,p2[i].second); for (i = 0; i < p3.size(); i++) tree3->update(0,r,p3[i].first,p3[i].second); for (i = 0; i < p4.size(); i++) tree4->update(0,r,p4[i].first,p4[i].second); } int colour(int ar,int ac,int br,int bc) { ar--,ac--,br--,bc--; LLI ans = 0; ans += (LLI) (br-ar+1)*(bc-ac+1)-tree1->query(0,r,ar+1,br+1,ac+1,bc+1); ans -= (LLI) (br-ar)*(bc-ac+1)-tree2->query(0,r,ar+1,br,ac+1,bc+1); ans -= (LLI) (br-ar+1)*(bc-ac)-tree3->query(0,r,ar+1,br+1,ac+1,bc); ans += (LLI) (br-ar)*(bc-ac)-tree4->query(0,r,ar+1,br,ac+1,bc); if ((ar < ly) && (br > ry) && (ac < lx) && (bc > rx)) ans++; return ans; }

Compilation message (stderr)

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:157:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < p1.size(); i++) tree1->update(0,r,p1[i].first,p1[i].second);
                 ~~^~~~~~~~~~~
rainbow.cpp:158:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < p2.size(); i++) tree2->update(0,r,p2[i].first,p2[i].second);
                 ~~^~~~~~~~~~~
rainbow.cpp:159:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < p3.size(); i++) tree3->update(0,r,p3[i].first,p3[i].second);
                 ~~^~~~~~~~~~~
rainbow.cpp:160:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < p4.size(); i++) tree4->update(0,r,p4[i].first,p4[i].second);
                 ~~^~~~~~~~~~~
#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...