oj.uz

Submission #405206

# Submission time Handle Problem Language Result Execution time Memory
405206 2021-05-15T21:55:12 Z gevacrt Street Lamps (APIO19_street_lamps) C++17
20 / 100
 5000 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, 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;
    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 << endl;
        }
    }

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 583 ms 3396 KB Output is correct
2 Correct 722 ms 5000 KB Output is correct
3 Correct 1433 ms 14888 KB Output is correct
4 Correct 4870 ms 390908 KB Output is correct
5 Correct 4742 ms 390620 KB Output is correct
6 Execution timed out 5010 ms 443908 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1612 KB Output is correct
2 Correct 6 ms 1356 KB Output is correct
3 Correct 6 ms 1216 KB Output is correct
4 Correct 4 ms 844 KB Output is correct
5 Runtime error 3184 ms 524292 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 972 KB Output is correct
2 Correct 6 ms 1484 KB Output is correct
3 Correct 8 ms 1484 KB Output is correct
4 Correct 6 ms 1512 KB Output is correct
5 Correct 3116 ms 195448 KB Output is correct
6 Correct 4763 ms 443628 KB Output is correct
7 Execution timed out 5077 ms 443692 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 583 ms 3396 KB Output is correct
9 Correct 722 ms 5000 KB Output is correct
10 Correct 1433 ms 14888 KB Output is correct
11 Correct 4870 ms 390908 KB Output is correct
12 Correct 4742 ms 390620 KB Output is correct
13 Execution timed out 5010 ms 443908 KB Time limit exceeded
14 Halted 0 ms 0 KB -