Submission #392096

#TimeUsernameProblemLanguageResultExecution timeMemory
392096MarcoMeijerLand of the Rainbow Gold (APIO17_rainbow)C++14
11 / 100
3095 ms472712 KiB
#include "rainbow.h" #include <bits/stdc++.h> using namespace std; // macros typedef long long ll; typedef long double ld; typedef pair<int, int> ii; typedef pair<ll, ll> lll; typedef tuple<int, int, int> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<iii> viii; typedef vector<ll> vll; typedef vector<lll> vlll; #define REP(a,b,c) for(int a=int(b); a<int(c); a++) #define RE(a,c) REP(a,0,c) #define RE1(a,c) REP(a,1,c+1) #define REI(a,b,c) REP(a,b,c+1) #define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--) #define FOR(a,b) for(auto& a : b) #define all(a) a.begin(), a.end() #define INF 1e9 #define EPS 1e-9 #define pb push_back #define popb pop_back #define fi first #define se second #define sz size() const int MX = (1<<22); const int N = (1<<19); int R, C, sr, sc, m; set<ii> blue; set<ii> points; set<ii> edges; int minR, maxR, minC, maxC; int root=0; struct QuadTree { int seg1[MX]; int point1[MX]; int child1[MX][2]; int nxt1=0; int seg2[MX]; int child2[MX][2]; int nxt2=1; QuadTree() { RE(i,MX) seg1[i]=0; RE(i,MX) seg2[i]=-1; RE(i,MX) RE(j,2) child1[i][j] = child2[i][j] = -1; } void add1(int x, int l, int r, int& p) { if(p == -1) p = nxt1++; seg1[p]++; if(l == r) return; int m = (l+r)/2; if(seg1[p] == 1) { point1[p] = x; return; } if(point1[p] != -1) { int y = point1[p]; if(y <= m) add1(y, l , m, child1[p][0]); else add1(y, m+1, r, child1[p][1]); point1[p] = -1; } if(x <= m) add1(x, l , m, child1[p][0]); else add1(x, m+1, r, child1[p][1]); } void add(int x, int y, int l=0, int r=N-1, int& p=root) { if(p == -1) p = nxt2++; add1(y, 0, N-1, seg2[p]); if(l == r) return; int m = (l+r)/2; if(x <= m) add(x, y, l , m, child2[p][0]); else add(x, y, m+1, r, child2[p][1]); } int get1(int i, int j, int l, int r, int p) { if(j < l || i > r) return 0; if(p == -1) return 0; if(i <= l && j >= r) return seg1[p]; if(point1[p] != -1) return i <= point1[p] && point1[p] <= j; int m = (l+r)/2; int a = get1(i, j, l , m, child1[p][0]); int b = get1(i, j, m+1, r, child1[p][1]); return a+b; } int get(int i, int j, int x, int y, int l=0, int r=N-1, int p=root) { if(j < l || i > r) return 0; if(p == -1) return 0; if(i <= l && j >= r) return get1(x,y,0,N-1,seg2[p]); int m = (l+r)/2; int a = get(i, j, x, y, l , m, child2[p][0]); int b = get(i, j, x, y, m+1, r, child2[p][1]); return a+b; } } blueCells, bluePoints, blueLandEdgesH, blueLandEdgesV; void init(int _R, int _C, int _sr, int _sc, int M, char *S) { R=_R; C=_C; sr=_sr; sc=_sc; minR=maxR=sr; minC=maxC=sc; RE(i,M) { blue.insert({sc,sr}); if(S[i] == 'N') sr--; if(S[i] == 'S') sr++; if(S[i] == 'E') sc++; if(S[i] == 'W') sc--; } blue.insert({sc,sr}); FOR(p,blue) { minR = min(minR, p.se); minC = min(minC, p.fi); maxR = max(maxR, p.se); maxC = max(maxC, p.fi); blueCells.add(p.fi,p.se); points.insert({p.fi ,p.se }); points.insert({p.fi ,p.se+1}); points.insert({p.fi+1,p.se }); points.insert({p.fi+1,p.se+1}); if(!blue.count({p.fi-1,p.se })) blueLandEdgesV.add(p.fi , p.se ); blueLandEdgesV.add(p.fi+1, p.se ); if(!blue.count({p.fi ,p.se-1})) blueLandEdgesH.add(p.fi , p.se ); blueLandEdgesH.add(p.fi , p.se+1); } FOR(p,points) bluePoints.add(p.fi,p.se); } int colour(int ar, int ac, int br, int bc) { int blueCellsCnt = blueCells .get(ac ,bc,ar ,br); int bluePointsCnt = bluePoints.get(ac+1,bc,ar+1,br); int blueLandEdges = blueLandEdgesH.get(ac,bc,ar+1,br) + blueLandEdgesV.get(ac+1,bc,ar,br); int W = bc - ac + 1; int H = br - ar + 1; int V = W*H - blueCellsCnt; int F = (W-1)*(H-1) - bluePointsCnt + 1; int E = (W-1)*H + (H-1)*W - blueLandEdges; if(ar < minR && maxR < br && ac < minC && maxC < bc) F++; return V - E + F - 1; }

Compilation message (stderr)

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:131:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  131 |         if(!blue.count({p.fi-1,p.se  })) blueLandEdgesV.add(p.fi  , p.se  );
      |         ^~
rainbow.cpp:132:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  132 |                                          blueLandEdgesV.add(p.fi+1, p.se  );
      |                                          ^~~~~~~~~~~~~~
rainbow.cpp:133:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  133 |         if(!blue.count({p.fi  ,p.se-1})) blueLandEdgesH.add(p.fi  , p.se  );
      |         ^~
rainbow.cpp:134:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  134 |                                          blueLandEdgesH.add(p.fi  , p.se+1);
      |                                          ^~~~~~~~~~~~~~
#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...