Submission #405208

#	Time	Username	Problem	Language	Result	Execution time	Memory
405208		gevacrt	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	4170 ms	293188 KiB

street_lamps

#include<bits/stdc++.h>
using namespace std;

#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

#define INF INT_MAX
#define MOD 1000000007
#define all(x) x.begin(), x.end()

namespace CC {
    set<ii> S;
    void merge(int x){ // merge x-1 and x
        auto r = S.lower_bound({x, x}), l = prev(r);

        S.insert({l->first, r->second});
        S.erase(l); S.erase(r);
    }

    void unmerge(int x){ // unmerge x-1 and x
        auto it = prev(S.lower_bound({x, x}));
        S.insert({it->first, x-1}); S.insert({x, it->second});
        S.erase(it);
    }

    ii query(int x){
        auto it = prev(S.lower_bound({x+1, x}));
        return {it->first, it->second};
    }

    void init(int N){
        for(int x = 1; x <= N; x++)
            S.insert({x, x});
    }
};

namespace BIT {
    gp_hash_table<int, int> arr[300010];
    int N;

    void update(int _x, int _y, int val){
        for(int x = _x; x <= N; x += x&-x)
            for(int y = _y; y <= N; y += y&-y)
                arr[x][y] += val;
    }

    int query(int _x, int _y){
        int ans = 0;
        for(int x = _x; x; x -= x&-x)
            for(int y = _y; y; y -= y&-y)
                if(arr[x].find(y) != arr[x].end())
                    ans += arr[x][y];
        return ans;
    }

    void update(int x1, int y1, int x2, int y2, int val){
        update(x1, y1, val); update(x2+1, y2+1, val); 
        update(x1, y2+1, -val); update(x2+1, y1, -val); 
    }
};

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, Q; cin >> N >> Q;
    BIT::N = N+10; CC::init(N+1); 


    vi isOn(N+1);
    for(int x = 1; x <= N; x++){
        char c; cin >> c;
        if(c == '1')
            CC::merge(x+1), isOn[x] = 1;
    }

    for(int q = 1; q <= Q; q++){
        string s; cin >> s;
        if(s == "toggle"){
            int x; cin >> x;
            auto l = CC::query(x).first, r = CC::query(x+1).second;
            
            if(isOn[x] == 1){
                BIT::update(l, x+1, x, r, q);
                CC::unmerge(x+1);
            }else{
                BIT::update(l, x+1, x, r, -q);
                CC::merge(x+1);
            }
            isOn[x] ^= 1;

        }else{
            int a, b; cin >> a >> b;
            int v = BIT::query(a,b);
            if(CC::query(a) == CC::query(b)) v += q;
            cout << v << "\n";
        }
    }

    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20