oj.uz

Submission #678865

# Submission time Handle Problem Language Result Execution time Memory
678865 2023-01-06T19:15:27 Z qwerasdfzxcl Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 541 ms 227080 KB 
#include "rainbow.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr int INF = 1e9+100;

struct Node{
    int l, r, x;
    Node(){}
    Node(int _l, int _r, int _x): l(_l), r(_r), x(_x) {}
};

struct PST{
    vector<Node> tree;
    vector<int> root;
    int sz;

    int cp(int x){
        tree.push_back(tree[x]);
        return (int)tree.size()-1;
    }
    void update(int i, int l, int r, int p, int x){
        tree[i].x += x;
        if (l==r) return;

        int m = (l+r)>>1;

        if (p <= m){
            tree[i].l = cp(tree[i].l);
            update(tree[i].l, l, m, p, x);
        }
        else{
            tree[i].r = cp(tree[i].r);
            update(tree[i].r, m+1, r, p, x);
        }
    }
    int query(int i, int l, int r, int s, int e){
        if (r<s || e<l) return 0;
        if (s<=l && r<=e) return tree[i].x;

        int m = (l+r)>>1;
        return query(tree[i].l, l, m, s, e) + query(tree[i].r, m+1, r, s, e);
    }

    void init(int n){
        sz = n;
        tree.emplace_back(0, 0, 0);
        root.push_back(0);
    }
    void add_root(){root.push_back(cp(root.back()));}
    void update(int p, int x){update(root.back(), 1, sz, p, x);}
    int query(int t, int l, int r){return query(root[t], 1, sz, l, r);}
    int query2D(int t1, int t2, int l, int r){return query(t2, l, r) - query(t1-1, l, r);}

}treeV, treeEh, treeEv, treeF;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}, n, m, mnx, mxx, mny, mxy;
vector<int> V[200200], Eh[200200], Ev[200200], F[200200];

void add_vertex(int x, int y){
    mnx = min(mnx, x);
    mxx = max(mxx, x);
    mny = min(mny, y);
    mxy = max(mxy, y);

    V[x].push_back(y);

    Eh[x].push_back(y-1);
    Eh[x].push_back(y);
    Ev[x-1].push_back(y);
    Ev[x].push_back(y);

    for (int i=-1;i<=0;i++){
        for (int j=-1;j<=0;j++){
            F[x+i].push_back(y+j);
        }
    }
}

void pst_init(vector<int> a[], PST &tree){
    tree.init(m);
    for (int i=1;i<=n;i++){
        sort(a[i].begin(), a[i].end());
        a[i].erase(unique(a[i].begin(), a[i].end()), a[i].end());

        tree.add_root();
        for (auto &y:a[i]) if (y>0) tree.update(y, 1);
    }
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    n = R, m = C;
    mnx = mny = 1e9;
    mxx = mxy = -1e9;
    add_vertex(sr, sc);

    for (int i=0;i<M;i++){
        int k;
        if (S[i]=='N') k = 0;
        if (S[i]=='E') k = 1;
        if (S[i]=='S') k = 2;
        if (S[i]=='W') k = 3;

        sr += dx[k], sc += dy[k];
        add_vertex(sr, sc);
    }

    pst_init(V, treeV);
    pst_init(Eh, treeEh);
    pst_init(Ev, treeEv);
    pst_init(F, treeF);
}


int colour(int ar, int ac, int br, int bc) {
    ll v = 0, e = 0, f = 0;
    if (ar < mnx && mxx < br && ac < mny && mxy < bc) f = 1;

    ll xL = br - ar, yL = bc - ac;

    v = xL * yL - treeV.query2D(ar, br, ac, bc);
    e = xL * (yL-1) - treeEh.query2D(ar, br, ac, bc-1);
    e += (xL-1) * yL - treeEv.query2D(ar, br-1, ac, bc);
    f = (xL-1) * (yL-1) - treeF.query2D(ar, br-1, ac, bc-1);

    return v - e + f;
}

Compilation message

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:105:32: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
  105 |         sr += dx[k], sc += dy[k];
      |                            ~~~~^

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19220 KB Output is correct
2 Correct 12 ms 19764 KB Output is correct
3 Incorrect 12 ms 19284 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 11 ms 19028 KB Output is correct
3 Correct 420 ms 111828 KB Output is correct
4 Correct 531 ms 177744 KB Output is correct
5 Correct 541 ms 169196 KB Output is correct
6 Correct 458 ms 126116 KB Output is correct
7 Correct 488 ms 122164 KB Output is correct
8 Correct 287 ms 25504 KB Output is correct
9 Correct 510 ms 177348 KB Output is correct
10 Correct 533 ms 175836 KB Output is correct
11 Correct 452 ms 126012 KB Output is correct
12 Correct 255 ms 174484 KB Output is correct
13 Correct 252 ms 177636 KB Output is correct
14 Correct 261 ms 176176 KB Output is correct
15 Correct 216 ms 126296 KB Output is correct
16 Correct 428 ms 116344 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19028 KB Output is correct
2 Correct 206 ms 209332 KB Output is correct
3 Correct 219 ms 227080 KB Output is correct
4 Correct 203 ms 212720 KB Output is correct
5 Correct 186 ms 192216 KB Output is correct
6 Correct 80 ms 72764 KB Output is correct
7 Incorrect 120 ms 107964 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19220 KB Output is correct
2 Correct 12 ms 19764 KB Output is correct
3 Incorrect 12 ms 19284 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19220 KB Output is correct
2 Correct 12 ms 19764 KB Output is correct
3 Incorrect 12 ms 19284 KB Output isn't correct
4 Halted 0 ms 0 KB -