oj.uz

Submission #392097

# Submission time Handle Problem Language Result Execution time Memory
392097 2021-04-20T13:43:40 Z MarcoMeijer Land of the Rainbow Gold (APIO17_rainbow) C++14
35 / 100
 3000 ms 866620 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<<23);
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 565 ms 788292 KB Output is correct
2 Correct 467 ms 788528 KB Output is correct
3 Correct 471 ms 788396 KB Output is correct
4 Correct 463 ms 788332 KB Output is correct
5 Correct 474 ms 788588 KB Output is correct
6 Correct 454 ms 788256 KB Output is correct
7 Correct 454 ms 788220 KB Output is correct
8 Correct 456 ms 788292 KB Output is correct
9 Correct 451 ms 788172 KB Output is correct
10 Correct 464 ms 788252 KB Output is correct
11 Correct 457 ms 788400 KB Output is correct
12 Correct 461 ms 788420 KB Output is correct
13 Correct 491 ms 788844 KB Output is correct
14 Correct 501 ms 788672 KB Output is correct
15 Correct 454 ms 788292 KB Output is correct
16 Correct 450 ms 788336 KB Output is correct
17 Correct 456 ms 788280 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 788336 KB Output is correct
2 Correct 456 ms 788280 KB Output is correct
3 Correct 2591 ms 826972 KB Output is correct
4 Execution timed out 3144 ms 851768 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 788292 KB Output is correct
2 Correct 2391 ms 851736 KB Output is correct
3 Correct 2591 ms 866592 KB Output is correct
4 Correct 2541 ms 864660 KB Output is correct
5 Correct 1994 ms 843372 KB Output is correct
6 Correct 842 ms 793412 KB Output is correct
7 Correct 1219 ms 797940 KB Output is correct
8 Correct 2154 ms 831156 KB Output is correct
9 Correct 1964 ms 824432 KB Output is correct
10 Correct 833 ms 794292 KB Output is correct
11 Correct 1421 ms 813004 KB Output is correct
12 Correct 2361 ms 851836 KB Output is correct
13 Correct 2606 ms 866568 KB Output is correct
14 Correct 2556 ms 864668 KB Output is correct
15 Correct 2025 ms 843372 KB Output is correct
16 Correct 755 ms 792496 KB Output is correct
17 Correct 1228 ms 798048 KB Output is correct
18 Correct 2394 ms 813600 KB Output is correct
19 Correct 2581 ms 859948 KB Output is correct
20 Correct 2490 ms 859992 KB Output is correct
21 Correct 2171 ms 831032 KB Output is correct
22 Correct 1964 ms 824476 KB Output is correct
23 Correct 858 ms 794336 KB Output is correct
24 Correct 1455 ms 813036 KB Output is correct
25 Correct 2399 ms 851768 KB Output is correct
26 Correct 2643 ms 866620 KB Output is correct
27 Correct 2577 ms 864676 KB Output is correct
28 Correct 2036 ms 843444 KB Output is correct
29 Correct 773 ms 792420 KB Output is correct
30 Correct 1255 ms 798040 KB Output is correct
31 Correct 2404 ms 813412 KB Output is correct
32 Correct 2636 ms 859944 KB Output is correct
33 Correct 2477 ms 859976 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 565 ms 788292 KB Output is correct
2 Correct 467 ms 788528 KB Output is correct
3 Correct 471 ms 788396 KB Output is correct
4 Correct 463 ms 788332 KB Output is correct
5 Correct 474 ms 788588 KB Output is correct
6 Correct 454 ms 788256 KB Output is correct
7 Correct 454 ms 788220 KB Output is correct
8 Correct 456 ms 788292 KB Output is correct
9 Correct 451 ms 788172 KB Output is correct
10 Correct 464 ms 788252 KB Output is correct
11 Correct 457 ms 788400 KB Output is correct
12 Correct 461 ms 788420 KB Output is correct
13 Correct 491 ms 788844 KB Output is correct
14 Correct 501 ms 788672 KB Output is correct
15 Correct 454 ms 788292 KB Output is correct
16 Correct 450 ms 788336 KB Output is correct
17 Correct 456 ms 788280 KB Output is correct
18 Execution timed out 3148 ms 807300 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 565 ms 788292 KB Output is correct
2 Correct 467 ms 788528 KB Output is correct
3 Correct 471 ms 788396 KB Output is correct
4 Correct 463 ms 788332 KB Output is correct
5 Correct 474 ms 788588 KB Output is correct
6 Correct 454 ms 788256 KB Output is correct
7 Correct 454 ms 788220 KB Output is correct
8 Correct 456 ms 788292 KB Output is correct
9 Correct 451 ms 788172 KB Output is correct
10 Correct 464 ms 788252 KB Output is correct
11 Correct 457 ms 788400 KB Output is correct
12 Correct 461 ms 788420 KB Output is correct
13 Correct 491 ms 788844 KB Output is correct
14 Correct 501 ms 788672 KB Output is correct
15 Correct 454 ms 788292 KB Output is correct
16 Correct 450 ms 788336 KB Output is correct
17 Correct 456 ms 788280 KB Output is correct
18 Execution timed out 3148 ms 807300 KB Time limit exceeded
19 Halted 0 ms 0 KB -