oj.uz

Submission #431825

# Submission time Handle Problem Language Result Execution time Memory
431825 2021-06-17T15:52:17 Z nvmdava Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 1277 ms 410984 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second

const int N = 200005;

struct Node{
    Node *l = NULL, *r = NULL;
    int 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;
    }
    int 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;
            }
        }
    }
    int 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) {
    return 1 - riv.query(x1, y1, x2, y2) - 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 7116 KB Output is correct
2 Correct 13 ms 9548 KB Output is correct
3 Incorrect 8 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 5 ms 6476 KB Output is correct
3 Correct 666 ms 248296 KB Output is correct
4 Correct 1167 ms 410904 KB Output is correct
5 Correct 1130 ms 405948 KB Output is correct
6 Correct 821 ms 309308 KB Output is correct
7 Correct 1070 ms 304288 KB Output is correct
8 Correct 75 ms 7236 KB Output is correct
9 Correct 1277 ms 410824 KB Output is correct
10 Correct 1227 ms 405812 KB Output is correct
11 Correct 939 ms 309248 KB Output is correct
12 Correct 831 ms 382900 KB Output is correct
13 Correct 891 ms 410980 KB Output is correct
14 Correct 965 ms 405864 KB Output is correct
15 Correct 675 ms 309696 KB Output is correct
16 Correct 754 ms 293020 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 807 ms 410984 KB Output is correct
3 Correct 724 ms 379160 KB Output is correct
4 Correct 741 ms 398388 KB Output is correct
5 Correct 534 ms 293956 KB Output is correct
6 Correct 143 ms 77636 KB Output is correct
7 Incorrect 268 ms 148348 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 7116 KB Output is correct
2 Correct 13 ms 9548 KB Output is correct
3 Incorrect 8 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 7116 KB Output is correct
2 Correct 13 ms 9548 KB Output is correct
3 Incorrect 8 ms 7244 KB Output isn't correct
4 Halted 0 ms 0 KB -