oj.uz

Submission #431833

# Submission time Handle Problem Language Result Execution time Memory
431833 2021-06-17T15:55:27 Z nvmdava Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 1165 ms 411044 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define ll long long
const int N = 200005;

struct Node{
    Node *l = NULL, *r = NULL;
    ll a;
    Node* update(int L, int R, int x){
        Node* res = new Node();
        res -> l = l;
        res -> r = r;
        res -> a = a;
        ++res -> a;
        if(L == R)
            return res;
        
        int m = (L + R) >> 1;
        if(x <= m){
            if(l == NULL)
                l = new Node();
            res -> l = l -> update(L, m, x);
        } else {
            if(r == NULL)
                r = new Node();
            res -> r = r -> update(m + 1, R, x);
        }
        return res;
    }
    ll query(int L, int R, int le, int ri){
        if(R < le || L > ri)
            return 0;
        if(le <= L && R <= ri)
            return a;
        int m = (L + R) >> 1;

        return (l == NULL ? 0 : l -> query(L, m, le, ri)) + (r == NULL ? 0 : r -> query(m + 1, R, le, ri));
    }
};

struct Grid{
    Node* seg[N];
    void build(set<pair<int, int> >& v){
        seg[0] = new Node();
        auto it = v.begin();
        for(int i = 1; i < N; ++i){
            seg[i] = seg[i - 1];
            while(it != v.end() && it -> ff == i){
                seg[i] = seg[i] -> update(1, N, it -> ss);
                ++it;
            }
        }
    }
    ll query(int x1, int y1, int x2, int y2){
        if(x1 > x2 || y1 > y2) return 0; 
        return seg[x2] -> query(1, N, y1, y2) - seg[x1 - 1] -> query(1, N, y1, y2);
    }
} riv, dot, lix, liy;

void init(int R, int C, int sr, int sc, int M, char *S) {
    set<pair<int, int> > rivs, dots, lixs, liys;
    rivs.insert({sr, sc});
    for(int i = 0; i < M; ++i){
        if(S[i] == 'N')
            --sr;
        if(S[i] == 'E')
            ++sc;
        if(S[i] == 'S')
            ++sr;
        if(S[i] == 'W')
            --sc;
        rivs.insert({sr, sc});
    }
    for(auto& a : rivs){
        dots.insert({a.ff, a.ss});
        dots.insert({a.ff, a.ss + 1});
        dots.insert({a.ff + 1, a.ss + 1});
        dots.insert({a.ff + 1, a.ss});
        lixs.insert({a.ff, a.ss});
        lixs.insert({a.ff, a.ss + 1});
        liys.insert({a.ff, a.ss});
        liys.insert({a.ff + 1, a.ss});
    }
    riv.build(rivs);
    dot.build(dots);
    lix.build(lixs);
    liy.build(liys);
}

int colour(int x1, int y1, int x2, int y2) {
    ll t = riv.query(x1, y1, x2, y2);
    if(t == 0) return 1;
    return 1 - t - dot.query(x1 + 1, y1 + 1, x2, y2) + lix.query(x1, y1 + 1, x2, y2) + liy.query(x1 + 1, y1, x2, y2);
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7124 KB Output is correct
2 Correct 13 ms 9528 KB Output is correct
3 Incorrect 9 ms 7244 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 6 ms 6476 KB Output is correct
2 Correct 6 ms 6476 KB Output is correct
3 Correct 665 ms 248232 KB Output is correct
4 Correct 1061 ms 410820 KB Output is correct
5 Correct 1165 ms 405952 KB Output is correct
6 Correct 796 ms 309316 KB Output is correct
7 Correct 942 ms 304192 KB Output is correct
8 Correct 73 ms 7236 KB Output is correct
9 Correct 1107 ms 410920 KB Output is correct
10 Correct 1149 ms 405824 KB Output is correct
11 Correct 858 ms 309188 KB Output is correct
12 Correct 838 ms 382980 KB Output is correct
13 Correct 856 ms 410836 KB Output is correct
14 Correct 873 ms 405820 KB Output is correct
15 Correct 679 ms 309736 KB Output is correct
16 Correct 756 ms 292828 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6476 KB Output is correct
2 Correct 777 ms 411044 KB Output is correct
3 Correct 667 ms 379128 KB Output is correct
4 Correct 748 ms 398384 KB Output is correct
5 Correct 525 ms 293988 KB Output is correct
6 Correct 138 ms 77640 KB Output is correct
7 Incorrect 274 ms 148316 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7124 KB Output is correct
2 Correct 13 ms 9528 KB Output is correct
3 Incorrect 9 ms 7244 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7124 KB Output is correct
2 Correct 13 ms 9528 KB Output is correct
3 Incorrect 9 ms 7244 KB Output isn't correct
4 Halted 0 ms 0 KB -