Submission #404995

#	Time	Username	Problem	Language	Result	Execution time	Memory
404995		gevacrt	Street Lamps (APIO19_street_lamps)	C++17	0 / 100	2704 ms	524292 KiB

street_lamps

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

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

#define int ll

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()

struct DISJOINT_SET_UNION {
    vi par, sz; int groups;
    DISJOINT_SET_UNION(int N){
        par.resize(N), sz.resize(N, 1);
        for(int x = 0; x < N; x++) par[x] = x;
        groups = N;
    }

    int parent(int x){
        if(par[x] == x) return x;
        return parent(par[x]);
    }

    void merge(int x, int y){
        x = parent(x), y = parent(y);
        if(sz[x] > sz[y]) swap(x, y);
        par[x] = y; sz[y] += sz[x];
        groups--;
    }

    void unmerge(int x, int y){
        if(sz[x] > sz[y]) swap(x, y);
        par[x] = x; sz[y] -= sz[x];
        groups++;
    }
};

namespace BIT {
    gp_hash_table<int, gp_hash_table<int, int>> arr;
    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)
                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;
    DISJOINT_SET_UNION DSU(N+2);
    BIT::N = N+5;

    auto find_left = [&](int x){
        int l = 1, r = x, P = DSU.parent(x);
        while(l < r){
            int m = (l+r)/2;
            if(DSU.parent(m) == P) r = m;
            else l = m+1;
        }
        return r;
    };

    auto find_right = [&](int x){
        int l = x, r = N+1, P = DSU.parent(x);
        while(l < r){
            int m = (l+r+1)/2;
            if(DSU.parent(m) == P) l = m;
            else r = m-1;
        }
        return l;
    };

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

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

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

    return 0;
}

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