Submission #210007

#	Time	Username	Problem	Language	Result	Execution time	Memory
210007		tatyam	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	2809 ms	58860 KiB

street_lamps

#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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20