oj.uz

Submission #431841

# Submission time Handle Problem Language Result Execution time Memory
431841 2021-06-17T15:58:15 Z nvmdava Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 1244 ms 410976 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;
int mnx, mny, mxx, mxy;
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});
    mnx = mxx = sr;
    mny = mxy = 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});
        mnx = min(mnx, sr);
        mxx = max(mxx, sr);
        mny = min(mny, sc);
        mxy = max(mxy, 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){
    if(x1 < mnx && mxx < x2 && y1 < mny && mxy < y2)
        return 1;
    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 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 5 ms 6476 KB Output is correct
2 Correct 5 ms 6476 KB Output is correct
3 Correct 732 ms 248284 KB Output is correct
4 Correct 1134 ms 410940 KB Output is correct
5 Correct 1122 ms 405904 KB Output is correct
6 Correct 795 ms 309360 KB Output is correct
7 Correct 992 ms 304308 KB Output is correct
8 Correct 77 ms 7360 KB Output is correct
9 Correct 1120 ms 410812 KB Output is correct
10 Correct 1244 ms 405832 KB Output is correct
11 Correct 884 ms 309176 KB Output is correct
12 Correct 764 ms 382988 KB Output is correct
13 Correct 802 ms 410796 KB Output is correct
14 Correct 824 ms 405820 KB Output is correct
15 Correct 683 ms 309696 KB Output is correct
16 Correct 764 ms 292788 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 750 ms 410976 KB Output is correct
3 Correct 700 ms 379264 KB Output is correct
4 Correct 734 ms 398604 KB Output is correct
5 Correct 511 ms 293984 KB Output is correct
6 Correct 148 ms 77560 KB Output is correct
7 Incorrect 278 ms 148284 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 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 8 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 -