oj.uz

Submission #337484

# Submission time Handle Problem Language Result Execution time Memory
337484 2020-12-21T02:10:11 Z thecodingwizard Land of the Rainbow Gold (APIO17_rainbow) C++11
11 / 100
 270 ms 101740 KB 
#include <bits/stdc++.h>
#include "rainbow.h"
using namespace std;

#define ii pair<int, int>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define F0R(i, n) for (int i = 0; i < n; i++)
#define FOR(i, a, b) for (int i = a; i < b; i++)

const int maxn = 2e5+10, maxst = 1e6;

int st[maxst], L[maxst], R[maxst], ctr = 0;

struct SegTree {
    map<int, set<int>> points;
    int roots[maxn];
    void add(int r, int c) {
        points[r].insert(c);
    }
    void build() {
        F0R(i, maxn) {
            roots[i] = i==0?0:roots[i-1];
            for (int p : points[i]) {
                update(roots[i], 0, maxn-1, p);
            }
        }
    }
    void update(int &node, int i, int j, int k) {
        st[ctr+1] = st[node];
        L[ctr+1] = L[node];
        R[ctr+1] = R[node];
        node = ctr+1;
        ctr++;

        st[node]++;

        if (i == j) return;

        int m = (i+j)/2;
        if (m >= k) {
            update(L[node], i, m, k);
        } else {
            update(R[node], m+1, j, k);
        }
    }

    int query(int r1, int c1, int r2, int c2) {
        //cout << r1 << " " << c1 << "; " << r2 << " "<< c2 << endl;
        //cout << query(roots[r2], c1, c2, 0, maxn-1) << ", " <<  (r1>0?query(roots[r1-1], c1, c2, 0, maxn-1):0) << endl;
        return query(roots[r2], c1, c2, 0, maxn-1) - (r1>0?query(roots[r1-1], c1, c2, 0, maxn-1):0);
    }

    int query(int node, int l, int r, int i, int j) {
        if (l <= i && j <= r) return st[node];
        if (l > j || r < i) return 0;
        return query(L[node], l, r, i, (i+j)/2) + query(R[node], l, r, (i+j)/2+1, j);
    }
} vertices, edges_horiz, edges_vert, rivers;

int min_r = maxn, min_c = maxn, max_r = 0, max_c = 0;
void addRiver(int r, int c) {
    min_r = min(min_r, r);
    max_r = max(max_r, r);
    min_c = min(min_c, c);
    max_c = max(max_c, c);
    vertices.add(r, c);
    vertices.add(r+1, c);
    vertices.add(r, c+1);
    vertices.add(r+1, c+1);
    edges_horiz.add(r, c);
    edges_horiz.add(r+1, c);
    edges_vert.add(r, c);
    edges_vert.add(r, c+1);
    rivers.add(r, c);
    //cout << "adding " << r << ", " << c << endl;
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    --sr; --sc;
    addRiver(sr, sc);
    F0R(i, M) {
        char c = S[i];
        if (c == 'N') sr--;
        else if (c == 'E') sc++;
        else if (c == 'S') sr++;
        else if (c == 'W') sc--;
        else assert(false);
        addRiver(sr, sc);
    }
    vertices.build();
    edges_horiz.build();
    edges_vert.build();
    rivers.build();
}

int colour(int ar, int ac, int br, int bc) {
    --ar; --ac;
    int riverCt = rivers.query(ar, ac, br-1, bc-1);
    int vertexCt = vertices.query(ar+1, ac+1, br-1, bc-1) + (br-ar-1)*2 + (bc-ac-1)*2 + 4;
    int edgeCt = edges_horiz.query(ar+1, ac, br-1, bc-1) + edges_vert.query(ar, ac+1, br-1, bc-1) + (br-ar)*2 + (bc-ac)*2;
    int connectedComponents = (ar < min_r && br-1 > max_r && ac < min_c && bc-1 > max_c) ? 2 : 1;
    int ans = edgeCt - vertexCt + 1 + connectedComponents - 1 - riverCt;
    //cout << ar << " "<< ac << " " << br << " " << bc << " " << riverCt << " " << vertexCt << " " << edgeCt << " " << connectedComponents << endl;
    return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 78956 KB Output is correct
2 Correct 219 ms 79980 KB Output is correct
3 Correct 215 ms 79084 KB Output is correct
4 Correct 214 ms 79084 KB Output is correct
5 Correct 221 ms 80236 KB Output is correct
6 Correct 219 ms 78700 KB Output is correct
7 Correct 210 ms 78572 KB Output is correct
8 Correct 223 ms 78700 KB Output is correct
9 Correct 214 ms 78700 KB Output is correct
10 Correct 225 ms 78700 KB Output is correct
11 Correct 222 ms 79212 KB Output is correct
12 Correct 219 ms 79724 KB Output is correct
13 Correct 223 ms 80724 KB Output is correct
14 Correct 221 ms 81260 KB Output is correct
15 Correct 212 ms 78700 KB Output is correct
16 Correct 214 ms 78572 KB Output is correct
17 Correct 212 ms 78572 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 78572 KB Output is correct
2 Correct 212 ms 78572 KB Output is correct
3 Runtime error 140 ms 58860 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 78700 KB Output is correct
2 Runtime error 270 ms 101740 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 78956 KB Output is correct
2 Correct 219 ms 79980 KB Output is correct
3 Correct 215 ms 79084 KB Output is correct
4 Correct 214 ms 79084 KB Output is correct
5 Correct 221 ms 80236 KB Output is correct
6 Correct 219 ms 78700 KB Output is correct
7 Correct 210 ms 78572 KB Output is correct
8 Correct 223 ms 78700 KB Output is correct
9 Correct 214 ms 78700 KB Output is correct
10 Correct 225 ms 78700 KB Output is correct
11 Correct 222 ms 79212 KB Output is correct
12 Correct 219 ms 79724 KB Output is correct
13 Correct 223 ms 80724 KB Output is correct
14 Correct 221 ms 81260 KB Output is correct
15 Correct 212 ms 78700 KB Output is correct
16 Correct 214 ms 78572 KB Output is correct
17 Correct 212 ms 78572 KB Output is correct
18 Runtime error 158 ms 54480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 78956 KB Output is correct
2 Correct 219 ms 79980 KB Output is correct
3 Correct 215 ms 79084 KB Output is correct
4 Correct 214 ms 79084 KB Output is correct
5 Correct 221 ms 80236 KB Output is correct
6 Correct 219 ms 78700 KB Output is correct
7 Correct 210 ms 78572 KB Output is correct
8 Correct 223 ms 78700 KB Output is correct
9 Correct 214 ms 78700 KB Output is correct
10 Correct 225 ms 78700 KB Output is correct
11 Correct 222 ms 79212 KB Output is correct
12 Correct 219 ms 79724 KB Output is correct
13 Correct 223 ms 80724 KB Output is correct
14 Correct 221 ms 81260 KB Output is correct
15 Correct 212 ms 78700 KB Output is correct
16 Correct 214 ms 78572 KB Output is correct
17 Correct 212 ms 78572 KB Output is correct
18 Runtime error 158 ms 54480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -