oj.uz

Submission #218327

# Submission time Handle Problem Language Result Execution time Memory
218327 2020-04-02T01:57:13 Z anonymous Land of the Rainbow Gold (APIO17_rainbow) C++14
74 / 100
 1163 ms 161528 KB 
#include "rainbow.h"
#include <set>
#include <utility>
#include <iostream>
#define MAXN 100005
using namespace std;

class PersistentSegtree {
    int ST[MAXN*40][3], R[MAXN*2], X[MAXN*2];
    int V=1, P=1;
    int upd(int ind, int l, int r, int cur) {
        if (l > ind || ind > r) {return(cur);}
        if (l == r) {
            ST[V][0] = ST[cur][0] + 1, V++;
            return(V-1);
        } else {
            int mid = (l + r) >> 1, at = V;
            V++;
            ST[at][1] = upd(ind, l, mid, ST[cur][1]);
            ST[at][2] = upd(ind, mid+1, r, ST[cur][2]);
            ST[at][0] = ST[ST[at][1]][0] + ST[ST[at][2]][0];
            return(at);
        }
    }
    int ask(int lo, int hi, int l, int r, int cur) {
        if (l > hi || r < lo || cur == 0) {return(0);}
        else if (lo <= l && hi >= r) {return(ST[cur][0]);}
        else {
            int mid = (l + r) >> 1;
            return(ask(lo, hi, l, mid, ST[cur][1])+
                   ask(lo, hi, mid+1, r, ST[cur][2]));
        }
    }
public:
    void put(int x, int y) {
        X[P] = x;
        R[P] = upd(y, 1, MAXN, R[P-1]);
        P++;
    }
    int lb(int x) {
        int lo = 0, hi = P;
        while (lo + 1 != hi) {
            int mid = (lo + hi) >> 1;
            if (X[mid] > x) {hi = mid;}
            else {lo = mid;}
        }
        return(lo);
    }
    int ask(int xlo, int ylo, int xhi, int yhi) {
        if (xlo > xhi || ylo > yhi) {return(0);}
        int ql = lb(xlo-1), qr = lb(xhi);
        return(ask(ylo, yhi, 1, MAXN, R[qr])-
               ask(ylo, yhi, 1, MAXN, R[ql]));
    }
} rT, vT, hT, VT;
int R,C;
set<pair<int,int> > rS, vS, hS, VS;

void init(int r, int c, int sr, int sc, int M, char *S) {
    R = r, C = c;
    int x = sr, y = sc; //cur
    for (int i=0; i<=M; i++) {
        rS.insert({x, y}); //river
        vS.insert({x,y}); //lines
        vS.insert({x,y+1});
        hS.insert({x,y});
        hS.insert({x+1,y});
        VS.insert({x,y}); //vertex
        VS.insert({x+1,y});
        VS.insert({x,y+1});
        VS.insert({x+1,y+1});
        if (i == M) {break;}
        switch(S[i]) {
            case 'N':
                x--;
                break;
            case 'S':
                x++;
                break;
            case 'W':
                y--;
                break;
            case 'E':
                y++;
                break;
        }
    }
    for (auto p: rS) {
        rT.put(p.first,p.second);
    }
    for (auto p: vS) {
        vT.put(p.first,p.second);
    }
    for (auto p: hS) {
        hT.put(p.first,p.second);
    }
    for (auto p: VS) {
        VT.put(p.first,p.second);
    }
}

int colour(int ar, int ac, int br, int bc) {
    int V = VT.ask(ar+1, ac+1, br, bc); 
    int Fr = rT.ask(ar, ac, br, bc);
    int E = hT.ask(ar+1, ac, br, bc) + vT.ask(ar, ac+1, br, bc);
    int ans = E - V - Fr + 1;
    if (V == VS.size()) {ans+=1;}
    return(ans);
}

Compilation message

rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:107:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (V == VS.size()) {ans+=1;}
         ~~^~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 640 KB Output is correct
2 Correct 11 ms 1664 KB Output is correct
3 Correct 9 ms 768 KB Output is correct
4 Correct 7 ms 768 KB Output is correct
5 Correct 11 ms 2048 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 8 ms 896 KB Output is correct
12 Correct 10 ms 1536 KB Output is correct
13 Correct 11 ms 2560 KB Output is correct
14 Correct 13 ms 2944 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 5 ms 512 KB Output is correct
17 Correct 4 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 432 ms 95072 KB Output is correct
4 Correct 634 ms 158616 KB Output is correct
5 Correct 648 ms 157416 KB Output is correct
6 Correct 535 ms 121520 KB Output is correct
7 Correct 643 ms 119288 KB Output is correct
8 Correct 93 ms 1272 KB Output is correct
9 Correct 667 ms 158584 KB Output is correct
10 Correct 684 ms 157328 KB Output is correct
11 Correct 573 ms 121464 KB Output is correct
12 Correct 425 ms 147576 KB Output is correct
13 Correct 453 ms 158584 KB Output is correct
14 Correct 472 ms 157436 KB Output is correct
15 Correct 451 ms 121596 KB Output is correct
16 Correct 453 ms 112376 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 334 ms 95736 KB Output is correct
3 Correct 357 ms 160248 KB Output is correct
4 Correct 377 ms 157944 KB Output is correct
5 Correct 279 ms 118520 KB Output is correct
6 Correct 90 ms 6648 KB Output is correct
7 Correct 218 ms 59256 KB Output is correct
8 Correct 369 ms 141052 KB Output is correct
9 Correct 360 ms 125304 KB Output is correct
10 Correct 112 ms 31736 KB Output is correct
11 Correct 242 ms 77816 KB Output is correct
12 Correct 325 ms 95736 KB Output is correct
13 Correct 363 ms 160248 KB Output is correct
14 Correct 360 ms 158200 KB Output is correct
15 Correct 286 ms 118648 KB Output is correct
16 Correct 116 ms 24184 KB Output is correct
17 Correct 207 ms 59384 KB Output is correct
18 Correct 356 ms 158200 KB Output is correct
19 Correct 376 ms 159096 KB Output is correct
20 Correct 409 ms 159096 KB Output is correct
21 Correct 370 ms 141048 KB Output is correct
22 Correct 369 ms 125432 KB Output is correct
23 Correct 107 ms 31712 KB Output is correct
24 Correct 228 ms 77816 KB Output is correct
25 Correct 325 ms 95736 KB Output is correct
26 Correct 355 ms 160248 KB Output is correct
27 Correct 363 ms 158072 KB Output is correct
28 Correct 286 ms 118776 KB Output is correct
29 Correct 120 ms 24056 KB Output is correct
30 Correct 202 ms 59384 KB Output is correct
31 Correct 341 ms 158072 KB Output is correct
32 Correct 377 ms 159176 KB Output is correct
33 Correct 375 ms 158968 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 640 KB Output is correct
2 Correct 11 ms 1664 KB Output is correct
3 Correct 9 ms 768 KB Output is correct
4 Correct 7 ms 768 KB Output is correct
5 Correct 11 ms 2048 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 8 ms 896 KB Output is correct
12 Correct 10 ms 1536 KB Output is correct
13 Correct 11 ms 2560 KB Output is correct
14 Correct 13 ms 2944 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 5 ms 512 KB Output is correct
17 Correct 4 ms 384 KB Output is correct
18 Correct 1040 ms 83728 KB Output is correct
19 Correct 305 ms 7496 KB Output is correct
20 Correct 235 ms 4472 KB Output is correct
21 Correct 272 ms 5112 KB Output is correct
22 Correct 291 ms 5948 KB Output is correct
23 Correct 309 ms 7416 KB Output is correct
24 Correct 249 ms 5112 KB Output is correct
25 Correct 282 ms 5756 KB Output is correct
26 Correct 295 ms 6264 KB Output is correct
27 Correct 451 ms 68216 KB Output is correct
28 Correct 348 ms 34936 KB Output is correct
29 Correct 430 ms 62840 KB Output is correct
30 Correct 806 ms 161528 KB Output is correct
31 Correct 9 ms 640 KB Output is correct
32 Correct 777 ms 69116 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 640 KB Output is correct
2 Correct 11 ms 1664 KB Output is correct
3 Correct 9 ms 768 KB Output is correct
4 Correct 7 ms 768 KB Output is correct
5 Correct 11 ms 2048 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 8 ms 896 KB Output is correct
12 Correct 10 ms 1536 KB Output is correct
13 Correct 11 ms 2560 KB Output is correct
14 Correct 13 ms 2944 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 5 ms 512 KB Output is correct
17 Correct 4 ms 384 KB Output is correct
18 Correct 1040 ms 83728 KB Output is correct
19 Correct 305 ms 7496 KB Output is correct
20 Correct 235 ms 4472 KB Output is correct
21 Correct 272 ms 5112 KB Output is correct
22 Correct 291 ms 5948 KB Output is correct
23 Correct 309 ms 7416 KB Output is correct
24 Correct 249 ms 5112 KB Output is correct
25 Correct 282 ms 5756 KB Output is correct
26 Correct 295 ms 6264 KB Output is correct
27 Correct 451 ms 68216 KB Output is correct
28 Correct 348 ms 34936 KB Output is correct
29 Correct 430 ms 62840 KB Output is correct
30 Correct 806 ms 161528 KB Output is correct
31 Correct 9 ms 640 KB Output is correct
32 Correct 777 ms 69116 KB Output is correct
33 Correct 334 ms 95736 KB Output is correct
34 Correct 357 ms 160248 KB Output is correct
35 Correct 377 ms 157944 KB Output is correct
36 Correct 279 ms 118520 KB Output is correct
37 Correct 90 ms 6648 KB Output is correct
38 Correct 218 ms 59256 KB Output is correct
39 Correct 369 ms 141052 KB Output is correct
40 Correct 360 ms 125304 KB Output is correct
41 Correct 112 ms 31736 KB Output is correct
42 Correct 242 ms 77816 KB Output is correct
43 Correct 325 ms 95736 KB Output is correct
44 Correct 363 ms 160248 KB Output is correct
45 Correct 360 ms 158200 KB Output is correct
46 Correct 286 ms 118648 KB Output is correct
47 Correct 116 ms 24184 KB Output is correct
48 Correct 207 ms 59384 KB Output is correct
49 Correct 356 ms 158200 KB Output is correct
50 Correct 376 ms 159096 KB Output is correct
51 Correct 409 ms 159096 KB Output is correct
52 Correct 370 ms 141048 KB Output is correct
53 Correct 369 ms 125432 KB Output is correct
54 Correct 107 ms 31712 KB Output is correct
55 Correct 228 ms 77816 KB Output is correct
56 Correct 325 ms 95736 KB Output is correct
57 Correct 355 ms 160248 KB Output is correct
58 Correct 363 ms 158072 KB Output is correct
59 Correct 286 ms 118776 KB Output is correct
60 Correct 120 ms 24056 KB Output is correct
61 Correct 202 ms 59384 KB Output is correct
62 Correct 341 ms 158072 KB Output is correct
63 Correct 377 ms 159176 KB Output is correct
64 Correct 375 ms 158968 KB Output is correct
65 Correct 1091 ms 144888 KB Output is correct
66 Correct 1163 ms 128764 KB Output is correct
67 Correct 462 ms 35136 KB Output is correct
68 Correct 534 ms 81276 KB Output is correct
69 Incorrect 506 ms 99320 KB Output isn't correct
70 Halted 0 ms 0 KB -