oj.uz

Submission #392087

# Submission time Handle Problem Language Result Execution time Memory
392087 2021-04-20T13:19:36 Z MarcoMeijer Land of the Rainbow Gold (APIO17_rainbow) C++14
35 / 100
 3000 ms 350204 KB 
#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<<18);
 
int R, C, sr, sc, m;
set<ii> blue;
set<ii> points;
set<ii> edges;
int minR, maxR, minC, maxC;
 
struct QuadTree {
    int pointX[MX][5];
    int pointY[MX][5];
    int tot[MX];
    int child[MX][4];
    int nxt=1;
    QuadTree() {
        RE(i,MX) tot[i]=0;
        RE(i,MX) RE(j,4) child[i][j] = -1;
    }
 
    void add(int x, int y, int l=0, int r=N-1, int u=0, int d=N-1, int p=0) {
        tot[p]++;
        if(tot[p] <= 5) {
            pointX[p][tot[p]-1] = x;
            pointY[p][tot[p]-1] = y;
            return;
        }
        if(l == r)
            return;
        int mh = (l+r)/2;
        int mv = (u+d)/2;
        int cd = 0;
        if(x <= mh) cd += 1, r=mh;
        else l=mh+1;
        if(y <= mv) cd += 2, d=mv;
        else u=mv+1;
        if(child[p][cd] == -1) child[p][cd] = nxt++;
        add(x,y,l,r,u,d,child[p][cd]);
    }
    int get(int a, int b, int x, int y, int l=0, int r=N-1, int u=0, int d=N-1, int p=0) {
        if(p == -1) return 0;
        if(b < l || a > r || y < u || x > d) return 0;
        if(a <= l && b >= r && x <= u && y >= d) return tot[p];
        int res = 0;
        RE(i,min(5,tot[p]))
            if(a <= pointX[p][i] && pointX[p][i] <= b && x <= pointY[p][i] && pointY[p][i] <= y)
                res++;
        if(tot[p] <= 5)
            return res;
        int mh = (l+r)/2;
        int mv = (u+d)/2;
        res += get(a,b,x,y, mh+1, r , mv+1, d , child[p][0]);
        res += get(a,b,x,y, l   , mh, mv+1, d , child[p][1]);
        res += get(a,b,x,y, mh+1, r , u   , mv, child[p][2]);
        res += get(a,b,x,y, l   , mh, u   , mv, child[p][3]);
        return res;
    }
} 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

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:114:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  114 |         if(!blue.count({p.fi-1,p.se  })) blueLandEdgesV.add(p.fi  , p.se  );
      |         ^~
rainbow.cpp:115:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  115 |                                          blueLandEdgesV.add(p.fi+1, p.se  );
      |                                          ^~~~~~~~~~~~~~
rainbow.cpp:116:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  116 |         if(!blue.count({p.fi  ,p.se-1})) blueLandEdgesH.add(p.fi  , p.se  );
      |         ^~
rainbow.cpp:117:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  117 |                                          blueLandEdgesH.add(p.fi  , p.se+1);
      |                                          ^~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 328736 KB Output is correct
2 Correct 202 ms 328852 KB Output is correct
3 Correct 204 ms 328644 KB Output is correct
4 Correct 203 ms 328772 KB Output is correct
5 Correct 206 ms 328912 KB Output is correct
6 Correct 195 ms 328656 KB Output is correct
7 Correct 193 ms 328616 KB Output is correct
8 Correct 202 ms 328660 KB Output is correct
9 Correct 195 ms 328664 KB Output is correct
10 Correct 194 ms 328584 KB Output is correct
11 Correct 211 ms 328672 KB Output is correct
12 Correct 203 ms 328796 KB Output is correct
13 Correct 212 ms 328900 KB Output is correct
14 Correct 212 ms 329016 KB Output is correct
15 Correct 192 ms 328580 KB Output is correct
16 Correct 193 ms 328552 KB Output is correct
17 Correct 197 ms 328644 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 328552 KB Output is correct
2 Correct 197 ms 328644 KB Output is correct
3 Execution timed out 3097 ms 340956 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 328580 KB Output is correct
2 Correct 379 ms 348748 KB Output is correct
3 Correct 390 ms 348740 KB Output is correct
4 Correct 382 ms 350148 KB Output is correct
5 Correct 342 ms 343740 KB Output is correct
6 Correct 238 ms 332716 KB Output is correct
7 Correct 272 ms 336520 KB Output is correct
8 Correct 335 ms 347144 KB Output is correct
9 Correct 319 ms 344900 KB Output is correct
10 Correct 231 ms 332816 KB Output is correct
11 Correct 285 ms 338628 KB Output is correct
12 Correct 384 ms 348760 KB Output is correct
13 Correct 390 ms 348592 KB Output is correct
14 Correct 396 ms 350204 KB Output is correct
15 Correct 333 ms 343620 KB Output is correct
16 Correct 230 ms 331972 KB Output is correct
17 Correct 269 ms 336548 KB Output is correct
18 Correct 372 ms 349744 KB Output is correct
19 Correct 392 ms 348692 KB Output is correct
20 Correct 390 ms 348788 KB Output is correct
21 Correct 345 ms 347140 KB Output is correct
22 Correct 324 ms 344936 KB Output is correct
23 Correct 232 ms 332880 KB Output is correct
24 Correct 279 ms 338608 KB Output is correct
25 Correct 378 ms 348740 KB Output is correct
26 Correct 384 ms 348580 KB Output is correct
27 Correct 387 ms 350148 KB Output is correct
28 Correct 337 ms 343668 KB Output is correct
29 Correct 232 ms 331844 KB Output is correct
30 Correct 276 ms 336608 KB Output is correct
31 Correct 384 ms 349764 KB Output is correct
32 Correct 391 ms 348776 KB Output is correct
33 Correct 403 ms 348740 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 328736 KB Output is correct
2 Correct 202 ms 328852 KB Output is correct
3 Correct 204 ms 328644 KB Output is correct
4 Correct 203 ms 328772 KB Output is correct
5 Correct 206 ms 328912 KB Output is correct
6 Correct 195 ms 328656 KB Output is correct
7 Correct 193 ms 328616 KB Output is correct
8 Correct 202 ms 328660 KB Output is correct
9 Correct 195 ms 328664 KB Output is correct
10 Correct 194 ms 328584 KB Output is correct
11 Correct 211 ms 328672 KB Output is correct
12 Correct 203 ms 328796 KB Output is correct
13 Correct 212 ms 328900 KB Output is correct
14 Correct 212 ms 329016 KB Output is correct
15 Correct 192 ms 328580 KB Output is correct
16 Correct 193 ms 328552 KB Output is correct
17 Correct 197 ms 328644 KB Output is correct
18 Execution timed out 3098 ms 341244 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 328736 KB Output is correct
2 Correct 202 ms 328852 KB Output is correct
3 Correct 204 ms 328644 KB Output is correct
4 Correct 203 ms 328772 KB Output is correct
5 Correct 206 ms 328912 KB Output is correct
6 Correct 195 ms 328656 KB Output is correct
7 Correct 193 ms 328616 KB Output is correct
8 Correct 202 ms 328660 KB Output is correct
9 Correct 195 ms 328664 KB Output is correct
10 Correct 194 ms 328584 KB Output is correct
11 Correct 211 ms 328672 KB Output is correct
12 Correct 203 ms 328796 KB Output is correct
13 Correct 212 ms 328900 KB Output is correct
14 Correct 212 ms 329016 KB Output is correct
15 Correct 192 ms 328580 KB Output is correct
16 Correct 193 ms 328552 KB Output is correct
17 Correct 197 ms 328644 KB Output is correct
18 Execution timed out 3098 ms 341244 KB Time limit exceeded
19 Halted 0 ms 0 KB -