oj.uz

Submission #405207

# Submission time Handle Problem Language Result Execution time Memory
405207 2021-05-15T22:00:37 Z gevacrt Street Lamps (APIO19_street_lamps) C++17
60 / 100
 4277 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()

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 91848 KB Output is correct
2 Correct 76 ms 91848 KB Output is correct
3 Correct 78 ms 91808 KB Output is correct
4 Correct 83 ms 91980 KB Output is correct
5 Correct 76 ms 91844 KB Output is correct
6 Correct 88 ms 91880 KB Output is correct
7 Correct 76 ms 91844 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 93116 KB Output is correct
2 Correct 412 ms 93304 KB Output is correct
3 Correct 806 ms 100624 KB Output is correct
4 Correct 3513 ms 394088 KB Output is correct
5 Correct 3410 ms 397204 KB Output is correct
6 Correct 3675 ms 408168 KB Output is correct
7 Correct 1188 ms 116612 KB Output is correct
8 Correct 833 ms 117996 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 92696 KB Output is correct
2 Correct 77 ms 92600 KB Output is correct
3 Correct 83 ms 92452 KB Output is correct
4 Correct 76 ms 91952 KB Output is correct
5 Runtime error 3992 ms 524292 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 91988 KB Output is correct
2 Correct 83 ms 92288 KB Output is correct
3 Correct 85 ms 92444 KB Output is correct
4 Correct 103 ms 92556 KB Output is correct
5 Correct 1992 ms 130720 KB Output is correct
6 Correct 3355 ms 355720 KB Output is correct
7 Correct 3895 ms 408168 KB Output is correct
8 Correct 4277 ms 449656 KB Output is correct
9 Correct 475 ms 96040 KB Output is correct
10 Correct 382 ms 94968 KB Output is correct
11 Correct 482 ms 96036 KB Output is correct
12 Correct 380 ms 95092 KB Output is correct
13 Correct 473 ms 96068 KB Output is correct
14 Correct 392 ms 94916 KB Output is correct
15 Correct 1444 ms 119716 KB Output is correct
16 Correct 740 ms 120928 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 91848 KB Output is correct
2 Correct 76 ms 91848 KB Output is correct
3 Correct 78 ms 91808 KB Output is correct
4 Correct 83 ms 91980 KB Output is correct
5 Correct 76 ms 91844 KB Output is correct
6 Correct 88 ms 91880 KB Output is correct
7 Correct 76 ms 91844 KB Output is correct
8 Correct 343 ms 93116 KB Output is correct
9 Correct 412 ms 93304 KB Output is correct
10 Correct 806 ms 100624 KB Output is correct
11 Correct 3513 ms 394088 KB Output is correct
12 Correct 3410 ms 397204 KB Output is correct
13 Correct 3675 ms 408168 KB Output is correct
14 Correct 1188 ms 116612 KB Output is correct
15 Correct 833 ms 117996 KB Output is correct
16 Correct 78 ms 92696 KB Output is correct
17 Correct 77 ms 92600 KB Output is correct
18 Correct 83 ms 92452 KB Output is correct
19 Correct 76 ms 91952 KB Output is correct
20 Runtime error 3992 ms 524292 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -