oj.uz

Submission #210007

# Submission time Handle Problem Language Result Execution time Memory
210007 2020-03-16T09:15:10 Z tatyam Street Lamps (APIO19_street_lamps) C++17
100 / 100
 2809 ms 58860 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int INF=0x3fffffff;
#define rep(n) for(int i=0;i<n;++i)
#define each(i,...) for(auto&& i:__VA_ARGS__)
#define all(i) begin(i),end(i)
#define Uniq(a) sort(all(a));a.erase(unique(all(a)),end(a))
template<class T, class U> bool chmin(T& a, const U& b){ if(a > b){ a = b; return 1; } return 0; }
template<class T, class U> bool chmax(T& a, const U& b){ if(a < b){ a = b; return 1; } return 0; }



struct Lazy{
    int type;
    int first, last, cnt;
    void operator+=(const Lazy& b){
        if(!type){
            *this = b;
            return;
        }
        cnt += b.cnt;
        if(type == 2) cnt += b.first - last;
        last = b.last;
        type = b.type;
    }
};
struct kdTree{
    kdTree *l = nullptr, *r = nullptr;
    Lazy val = {0, 0, 0, 0};
    int xmin = INF, xmax = -INF, ymin = INF, ymax = -INF;
    kdTree(vector<pii>::iterator from, vector<pii>::iterator to, bool divx = false){
        for(auto p = from; p != to; p++){
            auto& i = *p;
            chmin(xmin, i.first);
            chmax(xmax, i.first);
            chmin(ymin, i.second);
            chmax(ymax, i.second);
        }
        if(to - from == 1) return;
        auto p = from + (to - from) / 2;
        if(divx) nth_element(from, p, to, [](pii a, pii b){ return a.first < b.first; });
        else nth_element(from, p, to, [](pii a, pii b){ return a.second < b.second; });
        l = new kdTree(from, p, !divx);
        r = new kdTree(p, to, !divx);
    }
    void push(){
        if(!l) return;
        if(!val.type) return;
        l->val += val;
        r->val += val;
        val = {0, 0, 0, 0};
    }
    void query(int x1, int x2, int y1, int y2, const Lazy& x){ // [x1, x2] && [y1, y2]
        if(xmax < x1 || x2 < xmin || ymax < y1 || y2 < ymin) return;
        if(x1 <= xmin && xmax <= x2 && y1 <= ymin && ymax <= y2){
            val += x;
            return;
        }
        push();
        l->query(x1, x2, y1, y2, x);
        r->query(x1, x2, y1, y2, x);
    }
    int get(int x, int y, int time){
        if(!l) return val.cnt + (val.type == 2 ? time - val.last : 0);
        push();
        if(l->xmin <= x && x <= l->xmax && l->ymin <= y && y <= l->ymax){
            int ans = l->get(x, y, time);
            if(ans != -1) return ans;
        }
        if(r->xmin <= x && x <= r->xmax && r->ymin <= y && y <= r->ymax){
            return r->get(x, y, time);
        }
        return -1;
    }
};
signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    vector<pii> a;
    vector<pair<char, pii>> query(q);
    each(i, query){
        string s;
        cin >> s;
        i.first = s[0];
        int x, y = 2;
        cin >> x;
        if(i.first == 'q') cin >> y;
        x--; y -= 2;
        i.second = {x, y};
        if(i.first == 'q') a.emplace_back(x, y);
    }
    Uniq(a);
    kdTree tree(all(a));
    set<int> dark = {-1, n};
    tree.query(0, n, 0, n, {2, 0, 0, 0});
    rep(n) if(s[i] == '0'){
        auto p = dark.insert(i).first;
        int x1 = *prev(p) + 1, x2 = *next(p) - 1;
        tree.query(x1, i, i, x2, {1, 0, 0, 0});
    }
    rep(q){
        char c = query[i].first;
        int x, y, time = i + 1;
        tie(x, y) = query[i].second;
        if(c == 't'){
            s[x] ^= 1;
            if(s[x] == '1'){
                auto p = dark.find(x);
                int x1 = *prev(p) + 1, x2 = *next(p) - 1;
                tree.query(x1, x, x, x2, {2, time, time, 0});
                dark.erase(p);
            }
            else{
                auto p = dark.insert(x).first;
                int x1 = *prev(p) + 1, x2 = *next(p) - 1;
                tree.query(x1, x, x, x2, {1, time, time, 0});
            }
        }
        else{
            cout << tree.get(x, y, time) << '\n';
        }
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 6124 KB Output is correct
2 Correct 155 ms 6128 KB Output is correct
3 Correct 199 ms 6764 KB Output is correct
4 Correct 525 ms 27904 KB Output is correct
5 Correct 493 ms 29312 KB Output is correct
6 Correct 509 ms 25228 KB Output is correct
7 Correct 502 ms 44920 KB Output is correct
8 Correct 377 ms 32248 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 526 ms 18548 KB Output is correct
6 Correct 1230 ms 26120 KB Output is correct
7 Correct 1169 ms 34176 KB Output is correct
8 Correct 498 ms 46072 KB Output is correct
9 Correct 122 ms 6636 KB Output is correct
10 Correct 126 ms 7660 KB Output is correct
11 Correct 135 ms 7660 KB Output is correct
12 Correct 2809 ms 58812 KB Output is correct
13 Correct 500 ms 46200 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 1714 ms 51356 KB Output is correct
6 Correct 1408 ms 39552 KB Output is correct
7 Correct 1072 ms 27520 KB Output is correct
8 Correct 404 ms 11660 KB Output is correct
9 Correct 287 ms 14704 KB Output is correct
10 Correct 200 ms 4476 KB Output is correct
11 Correct 289 ms 14704 KB Output is correct
12 Correct 196 ms 4600 KB Output is correct
13 Correct 283 ms 14700 KB Output is correct
14 Correct 202 ms 4600 KB Output is correct
15 Correct 2792 ms 58860 KB Output is correct
16 Correct 493 ms 46072 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 140 ms 6124 KB Output is correct
9 Correct 155 ms 6128 KB Output is correct
10 Correct 199 ms 6764 KB Output is correct
11 Correct 525 ms 27904 KB Output is correct
12 Correct 493 ms 29312 KB Output is correct
13 Correct 509 ms 25228 KB Output is correct
14 Correct 502 ms 44920 KB Output is correct
15 Correct 377 ms 32248 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 6 ms 504 KB Output is correct
19 Correct 6 ms 376 KB Output is correct
20 Correct 526 ms 18548 KB Output is correct
21 Correct 1230 ms 26120 KB Output is correct
22 Correct 1169 ms 34176 KB Output is correct
23 Correct 498 ms 46072 KB Output is correct
24 Correct 122 ms 6636 KB Output is correct
25 Correct 126 ms 7660 KB Output is correct
26 Correct 135 ms 7660 KB Output is correct
27 Correct 2809 ms 58812 KB Output is correct
28 Correct 500 ms 46200 KB Output is correct
29 Correct 6 ms 504 KB Output is correct
30 Correct 6 ms 504 KB Output is correct
31 Correct 5 ms 376 KB Output is correct
32 Correct 5 ms 376 KB Output is correct
33 Correct 1714 ms 51356 KB Output is correct
34 Correct 1408 ms 39552 KB Output is correct
35 Correct 1072 ms 27520 KB Output is correct
36 Correct 404 ms 11660 KB Output is correct
37 Correct 287 ms 14704 KB Output is correct
38 Correct 200 ms 4476 KB Output is correct
39 Correct 289 ms 14704 KB Output is correct
40 Correct 196 ms 4600 KB Output is correct
41 Correct 283 ms 14700 KB Output is correct
42 Correct 202 ms 4600 KB Output is correct
43 Correct 2792 ms 58860 KB Output is correct
44 Correct 493 ms 46072 KB Output is correct
45 Correct 95 ms 4080 KB Output is correct
46 Correct 140 ms 4336 KB Output is correct
47 Correct 504 ms 18608 KB Output is correct
48 Correct 1255 ms 31488 KB Output is correct
49 Correct 147 ms 8044 KB Output is correct
50 Correct 140 ms 8044 KB Output is correct
51 Correct 153 ms 8172 KB Output is correct
52 Correct 217 ms 22500 KB Output is correct
53 Correct 219 ms 22500 KB Output is correct
54 Correct 210 ms 22500 KB Output is correct