oj.uz

Submission #680675

# Submission time Handle Problem Language Result Execution time Memory
680675 2023-01-11T13:49:46 Z 79brue Land of the Rainbow Gold (APIO17_rainbow) C++17
100 / 100
 1300 ms 468740 KB 
#include "rainbow.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

struct PST{
    struct Node{
        Node *lc, *rc;
        int sum;

        Node(int l, int r){
            sum = 0;
            if(l==r) lc = rc = nullptr;
            else{
                int m = (l+r)/2;
                lc = new Node(l, m);
                rc = new Node(m+1, r);
            }
        }

        Node(Node *lc, Node *rc, int sum): lc(lc), rc(rc), sum(sum){}

        ~Node(){
            if(lc) delete lc;
            if(rc) delete rc;
        }

        int query(int l, int r, int s, int e){
            if(r<s || e<l) return 0;
            if(s<=l && r<=e) return sum;
            int m = (l+r)>>1;
            return lc->query(l, m, s, e) + rc->query(m+1, r, s, e);
        }

        Node* update(int l, int r, int x, int v){
            if(l==r){
                Node* tmp = new Node(lc, rc, sum + v);
                return tmp;
            }
            int m = (l+r)>>1;
            Node* tmp = new Node(lc, rc, sum+v);
            if(x<=m) tmp->lc = lc->update(l, m, x, v);
            else     tmp->rc = rc->update(m+1, r, x, v);
            return tmp;
        }
    } *root = nullptr;
    int n;

    PST(){}
    Node *yHistory[200002];
    int yMaximum;

    void init(int _n){
        n = _n;
        root = new Node(0, n);
        for(int i=0; i<=200001; i++) yHistory[i] = nullptr;
        yMaximum = 0;
    }

    void update(int x, int y){
        while(yMaximum < y) yHistory[yMaximum++] = root;
        root = root->update(0, n, x, 1);
    }

    void finish(){
        while(yMaximum < 200001) yHistory[yMaximum++] = root;
    }

    int query(int xl, int xr, int yl, int yr){
//        printf("(%d - %d) = %d\n", yHistory[yr]->query(0, n, xl, xr), (yl == 0 ? 0 : yHistory[yl-1]->query(0, n, xl, xr)));
        return yHistory[yr]->query(0, n, xl, xr) - (yl == 0 ? 0 : yHistory[yl-1]->query(0, n, xl, xr));
    }
} vpst, ehpst, evpst, fpst;

struct Point{
    int x, y;
    Point(){}
    Point(int x, int y): x(x), y(y){}
    bool operator<(const Point &r)const{
        if(y!=r.y) return y<r.y;
        return x<r.x;
    }
    bool operator==(const Point &r)const{
        return x==r.x && y==r.y;
    }
};

int N, M;
int xMin = 1e9, xMax = -1e9, yMin = 1e9, yMax = -1e9;
vector<Point> vvec, ehvec, evvec, fvec;

void check(int X, int Y){
    xMin = min(xMin, X), yMin = min(yMin, Y);
    xMax = max(xMax, X), yMax = max(yMax, Y);

    vvec.push_back(Point(X, Y));

    if(Y!=1) ehvec.push_back(Point(X, Y-1));
    if(Y!=M) ehvec.push_back(Point(X, Y));

    if(X!=1) evvec.push_back(Point(X-1, Y));
    if(X!=N) evvec.push_back(Point(X, Y));

    if(Y!=1 && X!=1) fvec.push_back(Point(X-1, Y-1));
    if(Y!=M && X!=1) fvec.push_back(Point(X-1, Y));
    if(Y!=1 && X!=N) fvec.push_back(Point(X, Y-1));
    if(Y!=M && X!=N) fvec.push_back(Point(X, Y));
}

void update(PST &pst, vector<Point> &vec){
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());

    pst.init(N);
    for(Point p: vec){
        pst.update(p.x, p.y);
    }
    pst.finish();
}

void init(int R, int C, int sr, int sc, int K, char *S){
    N = R, M = C;
    vpst.init(N);
    ehpst.init(N);
    evpst.init(N);
    fpst.init(N);

    int x = sr, y = sc;
    check(x, y);
    for(int i=0; i<K; i++){
        if(S[i] == 'N') x--;
        else if(S[i] == 'E') y++;
        else if(S[i] == 'W') y--;
        else x++;
        check(x, y);
    }

    update(vpst, vvec);
    update(ehpst, ehvec);
    update(evpst, evvec);
    update(fpst, fvec);
}

int colour(int x1, int y1, int x2, int y2){
    ll V = ll(x2-x1+1) * ll(y2-y1+1) - vpst.query(x1, x2, y1, y2);
    ll EH = ll(x2-x1+1) * ll(y2-y1) - ehpst.query(x1, x2, y1, y2-1);
    ll EV = ll(x2-x1) * ll(y2-y1+1) - evpst.query(x1, x2-1, y1, y2);
    ll F = ll(x2-x1) * ll(y2-y1) - fpst.query(x1, x2-1, y1, y2-1);

    if(x1 < xMin && xMax < x2 && y1 < yMin && yMax < y2) F++;

//    printf("%lld %lld %lld %lld\n", V, EH, EV, F);

    return V-(EH+EV)+F;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6740 KB Output is correct
2 Correct 8 ms 7636 KB Output is correct
3 Correct 5 ms 6864 KB Output is correct
4 Correct 6 ms 6872 KB Output is correct
5 Correct 8 ms 7896 KB Output is correct
6 Correct 4 ms 6484 KB Output is correct
7 Correct 4 ms 6484 KB Output is correct
8 Correct 4 ms 6472 KB Output is correct
9 Correct 4 ms 6484 KB Output is correct
10 Correct 4 ms 6484 KB Output is correct
11 Correct 6 ms 6996 KB Output is correct
12 Correct 6 ms 7512 KB Output is correct
13 Correct 7 ms 8276 KB Output is correct
14 Correct 10 ms 8848 KB Output is correct
15 Correct 4 ms 6484 KB Output is correct
16 Correct 3 ms 6484 KB Output is correct
17 Correct 4 ms 6472 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 4 ms 6472 KB Output is correct
3 Correct 131 ms 33204 KB Output is correct
4 Correct 177 ms 49076 KB Output is correct
5 Correct 165 ms 48024 KB Output is correct
6 Correct 141 ms 38284 KB Output is correct
7 Correct 143 ms 38496 KB Output is correct
8 Correct 103 ms 15852 KB Output is correct
9 Correct 163 ms 49152 KB Output is correct
10 Correct 185 ms 48108 KB Output is correct
11 Correct 145 ms 38260 KB Output is correct
12 Correct 114 ms 45920 KB Output is correct
13 Correct 139 ms 49048 KB Output is correct
14 Correct 111 ms 48036 KB Output is correct
15 Correct 103 ms 38240 KB Output is correct
16 Correct 136 ms 38588 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6484 KB Output is correct
2 Correct 518 ms 458360 KB Output is correct
3 Correct 579 ms 465028 KB Output is correct
4 Correct 629 ms 465132 KB Output is correct
5 Correct 462 ms 374768 KB Output is correct
6 Correct 250 ms 179600 KB Output is correct
7 Correct 318 ms 245036 KB Output is correct
8 Correct 113 ms 56408 KB Output is correct
9 Correct 133 ms 62368 KB Output is correct
10 Correct 178 ms 123408 KB Output is correct
11 Correct 267 ms 205304 KB Output is correct
12 Correct 491 ms 458508 KB Output is correct
13 Correct 584 ms 465148 KB Output is correct
14 Correct 536 ms 465048 KB Output is correct
15 Correct 463 ms 374680 KB Output is correct
16 Correct 232 ms 166316 KB Output is correct
17 Correct 338 ms 245140 KB Output is correct
18 Correct 555 ms 464196 KB Output is correct
19 Correct 490 ms 402068 KB Output is correct
20 Correct 476 ms 401808 KB Output is correct
21 Correct 130 ms 56236 KB Output is correct
22 Correct 125 ms 62428 KB Output is correct
23 Correct 196 ms 123388 KB Output is correct
24 Correct 313 ms 205332 KB Output is correct
25 Correct 573 ms 458448 KB Output is correct
26 Correct 639 ms 465044 KB Output is correct
27 Correct 539 ms 465052 KB Output is correct
28 Correct 497 ms 374764 KB Output is correct
29 Correct 304 ms 166348 KB Output is correct
30 Correct 315 ms 245120 KB Output is correct
31 Correct 591 ms 464152 KB Output is correct
32 Correct 468 ms 401960 KB Output is correct
33 Correct 455 ms 401912 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6740 KB Output is correct
2 Correct 8 ms 7636 KB Output is correct
3 Correct 5 ms 6864 KB Output is correct
4 Correct 6 ms 6872 KB Output is correct
5 Correct 8 ms 7896 KB Output is correct
6 Correct 4 ms 6484 KB Output is correct
7 Correct 4 ms 6484 KB Output is correct
8 Correct 4 ms 6472 KB Output is correct
9 Correct 4 ms 6484 KB Output is correct
10 Correct 4 ms 6484 KB Output is correct
11 Correct 6 ms 6996 KB Output is correct
12 Correct 6 ms 7512 KB Output is correct
13 Correct 7 ms 8276 KB Output is correct
14 Correct 10 ms 8848 KB Output is correct
15 Correct 4 ms 6484 KB Output is correct
16 Correct 3 ms 6484 KB Output is correct
17 Correct 4 ms 6472 KB Output is correct
18 Correct 624 ms 119696 KB Output is correct
19 Correct 180 ms 13656 KB Output is correct
20 Correct 121 ms 10592 KB Output is correct
21 Correct 173 ms 11412 KB Output is correct
22 Correct 162 ms 12476 KB Output is correct
23 Correct 152 ms 13488 KB Output is correct
24 Correct 125 ms 11276 KB Output is correct
25 Correct 156 ms 12112 KB Output is correct
26 Correct 183 ms 12956 KB Output is correct
27 Correct 378 ms 101432 KB Output is correct
28 Correct 339 ms 58092 KB Output is correct
29 Correct 390 ms 94504 KB Output is correct
30 Correct 629 ms 223512 KB Output is correct
31 Correct 6 ms 6612 KB Output is correct
32 Correct 556 ms 102736 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6740 KB Output is correct
2 Correct 8 ms 7636 KB Output is correct
3 Correct 5 ms 6864 KB Output is correct
4 Correct 6 ms 6872 KB Output is correct
5 Correct 8 ms 7896 KB Output is correct
6 Correct 4 ms 6484 KB Output is correct
7 Correct 4 ms 6484 KB Output is correct
8 Correct 4 ms 6472 KB Output is correct
9 Correct 4 ms 6484 KB Output is correct
10 Correct 4 ms 6484 KB Output is correct
11 Correct 6 ms 6996 KB Output is correct
12 Correct 6 ms 7512 KB Output is correct
13 Correct 7 ms 8276 KB Output is correct
14 Correct 10 ms 8848 KB Output is correct
15 Correct 4 ms 6484 KB Output is correct
16 Correct 3 ms 6484 KB Output is correct
17 Correct 4 ms 6472 KB Output is correct
18 Correct 624 ms 119696 KB Output is correct
19 Correct 180 ms 13656 KB Output is correct
20 Correct 121 ms 10592 KB Output is correct
21 Correct 173 ms 11412 KB Output is correct
22 Correct 162 ms 12476 KB Output is correct
23 Correct 152 ms 13488 KB Output is correct
24 Correct 125 ms 11276 KB Output is correct
25 Correct 156 ms 12112 KB Output is correct
26 Correct 183 ms 12956 KB Output is correct
27 Correct 378 ms 101432 KB Output is correct
28 Correct 339 ms 58092 KB Output is correct
29 Correct 390 ms 94504 KB Output is correct
30 Correct 629 ms 223512 KB Output is correct
31 Correct 6 ms 6612 KB Output is correct
32 Correct 556 ms 102736 KB Output is correct
33 Correct 518 ms 458360 KB Output is correct
34 Correct 579 ms 465028 KB Output is correct
35 Correct 629 ms 465132 KB Output is correct
36 Correct 462 ms 374768 KB Output is correct
37 Correct 250 ms 179600 KB Output is correct
38 Correct 318 ms 245036 KB Output is correct
39 Correct 113 ms 56408 KB Output is correct
40 Correct 133 ms 62368 KB Output is correct
41 Correct 178 ms 123408 KB Output is correct
42 Correct 267 ms 205304 KB Output is correct
43 Correct 491 ms 458508 KB Output is correct
44 Correct 584 ms 465148 KB Output is correct
45 Correct 536 ms 465048 KB Output is correct
46 Correct 463 ms 374680 KB Output is correct
47 Correct 232 ms 166316 KB Output is correct
48 Correct 338 ms 245140 KB Output is correct
49 Correct 555 ms 464196 KB Output is correct
50 Correct 490 ms 402068 KB Output is correct
51 Correct 476 ms 401808 KB Output is correct
52 Correct 130 ms 56236 KB Output is correct
53 Correct 125 ms 62428 KB Output is correct
54 Correct 196 ms 123388 KB Output is correct
55 Correct 313 ms 205332 KB Output is correct
56 Correct 573 ms 458448 KB Output is correct
57 Correct 639 ms 465044 KB Output is correct
58 Correct 539 ms 465052 KB Output is correct
59 Correct 497 ms 374764 KB Output is correct
60 Correct 304 ms 166348 KB Output is correct
61 Correct 315 ms 245120 KB Output is correct
62 Correct 591 ms 464152 KB Output is correct
63 Correct 468 ms 401960 KB Output is correct
64 Correct 455 ms 401912 KB Output is correct
65 Correct 131 ms 33204 KB Output is correct
66 Correct 177 ms 49076 KB Output is correct
67 Correct 165 ms 48024 KB Output is correct
68 Correct 141 ms 38284 KB Output is correct
69 Correct 143 ms 38496 KB Output is correct
70 Correct 103 ms 15852 KB Output is correct
71 Correct 163 ms 49152 KB Output is correct
72 Correct 185 ms 48108 KB Output is correct
73 Correct 145 ms 38260 KB Output is correct
74 Correct 114 ms 45920 KB Output is correct
75 Correct 139 ms 49048 KB Output is correct
76 Correct 111 ms 48036 KB Output is correct
77 Correct 103 ms 38240 KB Output is correct
78 Correct 136 ms 38588 KB Output is correct
79 Correct 304 ms 59812 KB Output is correct
80 Correct 302 ms 65828 KB Output is correct
81 Correct 503 ms 127000 KB Output is correct
82 Correct 674 ms 208852 KB Output is correct
83 Correct 1127 ms 461860 KB Output is correct
84 Correct 1300 ms 468632 KB Output is correct
85 Correct 1121 ms 468740 KB Output is correct
86 Correct 1059 ms 378196 KB Output is correct
87 Correct 866 ms 169880 KB Output is correct
88 Correct 917 ms 248740 KB Output is correct
89 Correct 1106 ms 467584 KB Output is correct
90 Correct 1076 ms 405524 KB Output is correct
91 Correct 955 ms 405316 KB Output is correct