oj.uz

Submission #392096

# Submission time Handle Problem Language Result Execution time Memory
392096 2021-04-20T13:42:35 Z MarcoMeijer Land of the Rainbow Gold (APIO17_rainbow) C++14
11 / 100
 3000 ms 472712 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<<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

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);
      |                                          ^~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 394436 KB Output is correct
2 Correct 240 ms 394560 KB Output is correct
3 Correct 234 ms 394436 KB Output is correct
4 Correct 236 ms 394300 KB Output is correct
5 Correct 245 ms 394564 KB Output is correct
6 Correct 222 ms 394404 KB Output is correct
7 Correct 225 ms 394212 KB Output is correct
8 Correct 225 ms 394192 KB Output is correct
9 Correct 226 ms 394300 KB Output is correct
10 Correct 226 ms 394372 KB Output is correct
11 Correct 234 ms 394308 KB Output is correct
12 Correct 240 ms 394392 KB Output is correct
13 Correct 249 ms 394556 KB Output is correct
14 Correct 255 ms 394660 KB Output is correct
15 Correct 223 ms 394308 KB Output is correct
16 Correct 218 ms 394248 KB Output is correct
17 Correct 222 ms 394180 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 394248 KB Output is correct
2 Correct 222 ms 394180 KB Output is correct
3 Correct 2309 ms 435492 KB Output is correct
4 Execution timed out 3095 ms 460300 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 394308 KB Output is correct
2 Correct 2118 ms 457816 KB Output is correct
3 Incorrect 2338 ms 472712 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 394436 KB Output is correct
2 Correct 240 ms 394560 KB Output is correct
3 Correct 234 ms 394436 KB Output is correct
4 Correct 236 ms 394300 KB Output is correct
5 Correct 245 ms 394564 KB Output is correct
6 Correct 222 ms 394404 KB Output is correct
7 Correct 225 ms 394212 KB Output is correct
8 Correct 225 ms 394192 KB Output is correct
9 Correct 226 ms 394300 KB Output is correct
10 Correct 226 ms 394372 KB Output is correct
11 Correct 234 ms 394308 KB Output is correct
12 Correct 240 ms 394392 KB Output is correct
13 Correct 249 ms 394556 KB Output is correct
14 Correct 255 ms 394660 KB Output is correct
15 Correct 223 ms 394308 KB Output is correct
16 Correct 218 ms 394248 KB Output is correct
17 Correct 222 ms 394180 KB Output is correct
18 Execution timed out 3086 ms 413904 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 394436 KB Output is correct
2 Correct 240 ms 394560 KB Output is correct
3 Correct 234 ms 394436 KB Output is correct
4 Correct 236 ms 394300 KB Output is correct
5 Correct 245 ms 394564 KB Output is correct
6 Correct 222 ms 394404 KB Output is correct
7 Correct 225 ms 394212 KB Output is correct
8 Correct 225 ms 394192 KB Output is correct
9 Correct 226 ms 394300 KB Output is correct
10 Correct 226 ms 394372 KB Output is correct
11 Correct 234 ms 394308 KB Output is correct
12 Correct 240 ms 394392 KB Output is correct
13 Correct 249 ms 394556 KB Output is correct
14 Correct 255 ms 394660 KB Output is correct
15 Correct 223 ms 394308 KB Output is correct
16 Correct 218 ms 394248 KB Output is correct
17 Correct 222 ms 394180 KB Output is correct
18 Execution timed out 3086 ms 413904 KB Time limit exceeded
19 Halted 0 ms 0 KB -