oj.uz

답안 #405004

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
405004 2021-05-15T13:56:06 Z gevacrt 가로등 (APIO19_street_lamps) C++17
0 / 100
 2971 ms 524292 KB 
#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(par[y] == x) swap(x, y);
        assert(par[x] == y);
        
        for(int py = par[x], P = parent(y); ; py = par[py]){
            sz[py] -= sz[x];
            if(py == P) break;
        }
    }
};

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)
                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;
    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.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 588 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1484 KB Output is correct
2 Correct 5 ms 1356 KB Output is correct
3 Correct 5 ms 1228 KB Output is correct
4 Correct 2 ms 844 KB Output is correct
5 Runtime error 2971 ms 524292 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 588 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -