oj.uz

Submission #431822

# Submission time Handle Problem Language Result Execution time Memory
431822 2021-06-17T15:50:25 Z nvmdava Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 1304 ms 413732 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){
        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 8 ms 7160 KB Output is correct
2 Correct 13 ms 9676 KB Output is correct
3 Incorrect 9 ms 7308 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 6572 KB Output is correct
3 Correct 780 ms 251084 KB Output is correct
4 Correct 1219 ms 413732 KB Output is correct
5 Correct 1288 ms 408736 KB Output is correct
6 Correct 914 ms 312328 KB Output is correct
7 Correct 1076 ms 307180 KB Output is correct
8 Correct 98 ms 10180 KB Output is correct
9 Correct 1304 ms 413704 KB Output is correct
10 Correct 1246 ms 408676 KB Output is correct
11 Correct 938 ms 312168 KB Output is correct
12 Correct 881 ms 385888 KB Output is correct
13 Correct 885 ms 413584 KB Output is correct
14 Correct 900 ms 408708 KB Output is correct
15 Correct 722 ms 312492 KB Output is correct
16 Correct 852 ms 295624 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6476 KB Output is correct
2 Correct 799 ms 410976 KB Output is correct
3 Correct 704 ms 379256 KB Output is correct
4 Correct 785 ms 398552 KB Output is correct
5 Correct 574 ms 294088 KB Output is correct
6 Correct 143 ms 77736 KB Output is correct
7 Incorrect 348 ms 148324 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7160 KB Output is correct
2 Correct 13 ms 9676 KB Output is correct
3 Incorrect 9 ms 7308 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7160 KB Output is correct
2 Correct 13 ms 9676 KB Output is correct
3 Incorrect 9 ms 7308 KB Output isn't correct
4 Halted 0 ms 0 KB -