oj.uz

Submission #798679

# Submission time Handle Problem Language Result Execution time Memory
798679 2023-07-30T22:51:37 Z gg123_pe Street Lamps (APIO19_street_lamps) C++14
60 / 100
 1199 ms 167660 KB 
#include <bits/stdc++.h> 
using namespace std; 

typedef long long ll; 

#define f(i,a,b) for(int i = a; i < b; i++)
const int N = 3e5 + 5, M = 1000;
const int RA = 1e6 + 5; 

int n, q; 
ll a[M][M]; 

void subtask_1(){
    f(i,1,q+1){
        f(j,1,n+1) a[i][j] = a[i-1][j]; 
        string ty; 
        ll x, y;

        cin >> ty; 
        if(ty[0] == 'q'){
            cin >> x >> y; 
            // cuantos tiempos el rango [x, y-1] suma 0
            int ans = 0; 
            f(j,0,i){
                int sum = 0; 
                f(r,x,y) sum += a[j][r]; 
                if(sum == 0) ans++; 
            }
            cout << ans << "\n"; 
        }
        else{
            cin >> x; 
            a[i][x] = 1 - a[i][x]; 
        }
    }
}

ll A[RA], root[RA]; 
vector <ll> L, R, st; 
ll ti[RA], X[RA], Y[RA]; 

int createLeaf(int val){
    L.push_back(-1), R.push_back(-1); 
    st.push_back(val); 
    return L.size() - 1; 
}
int createNode(int u, int v){
    L.push_back(u), R.push_back(v); 
    st.push_back(st[u] + st[v]); 
    return L.size() - 1; 
}
int build(int l, int r){
    if(l == r) return createLeaf(A[l]); 
    int m = (l+r)>>1; 
    return createNode(build(l, m), build(m+1, r)); 
}
int upd(int id, int l, int r, int pos, int val){
    if(l == r) return createLeaf(val); 
    int m = (l+r)>>1; 
    if(pos <= m) return createNode(upd(L[id], l, m, pos, val), R[id]);
    return createNode(L[id], upd(R[id], m+1, r, pos, val));  
}
int Query(int id, int l, int r, int x, int y){
    if(r < x or y < l) return 0; 
    if(x <= l and r <= y) return st[id]; 
    int m = (l+r)>>1; 
    return Query(L[id], l, m, x, y) + Query(R[id], m+1, r, x, y); 
}
void subtask_3(){
    root[0] = build(1, n); 

    f(i,1,q+1){
        root[i] = root[i-1]; 

        if(ti[i] == 0){
            ll x = X[i], y = Y[i]; 
            y--; 

            int ans = 0; 
            if(Query(root[i-1], 1, n, x, y) == 0){
                int l = 0, r = i-1; 
                while(l < r){
                    int m = (l+r)>>1; 
                    if(Query(root[m], 1, n, x, y) == 0) r = m; 
                    else l = m+1; 
                }
                ans = i - l; 
            }
            cout << ans << "\n"; 
        }
        else{
            int x = X[i]; 
            root[i] = upd(root[i], 1, n, x, 0); 
        }
    }
}
ll curr[RA]; 
ll start[RA]; 

void subtask_2(){
    f(i,1,q+1){
        int x = X[i]; 
        if(ti[i] == 0){
            ll tot = curr[x]; 

            if(A[x] == 0){
                tot += (i - start[x]); 
            }
            cout << tot << "\n"; 
        }
        else{
            if(A[x] == 0){
                curr[x] += i - start[x]; 
            }
            else{
                start[x] = i; 
            }
            A[x] = 1 - A[x]; 
        }
    }
}
int main(){
    cin >> n >> q; 

    string s; 
    cin >> s; 
    f(i,0,n){
        if(s[i] == '0') a[0][i+1] = A[i+1] = 1; 
        else a[0][i+1] = A[i+1] = 0; 
    }

    if(n <= 100 and q <= 100){
        subtask_1(); 
        return 0; 
    }
    bool flag = true; 

    f(i,1,q+1){
        string sa; 
        cin >> sa; 

        if(sa[0] == 'q'){
            cin >> X[i] >> Y[i]; 
            if(Y[i] != X[i] + 1) flag = false; 
        }
        else{
            ti[i] = 1; 
            cin >> X[i]; 
        }
    }

    if(flag) {
        subtask_2(); 
        return 0; 
    }
    subtask_3(); 
    return 0; 
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 704 KB Output is correct
5 Correct 1 ms 700 KB Output is correct
6 Correct 1 ms 828 KB Output is correct
7 Correct 1 ms 724 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 8584 KB Output is correct
2 Correct 131 ms 8652 KB Output is correct
3 Correct 144 ms 8820 KB Output is correct
4 Correct 175 ms 22832 KB Output is correct
5 Correct 178 ms 21140 KB Output is correct
6 Correct 165 ms 20448 KB Output is correct
7 Correct 214 ms 16672 KB Output is correct
8 Correct 205 ms 18124 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 493 ms 167660 KB Output is correct
6 Correct 543 ms 151528 KB Output is correct
7 Correct 506 ms 89140 KB Output is correct
8 Correct 1199 ms 34940 KB Output is correct
9 Correct 213 ms 9916 KB Output is correct
10 Correct 221 ms 10756 KB Output is correct
11 Correct 253 ms 10852 KB Output is correct
12 Correct 377 ms 33604 KB Output is correct
13 Correct 1126 ms 34964 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Incorrect 1 ms 596 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 704 KB Output is correct
5 Correct 1 ms 700 KB Output is correct
6 Correct 1 ms 828 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 122 ms 8584 KB Output is correct
9 Correct 131 ms 8652 KB Output is correct
10 Correct 144 ms 8820 KB Output is correct
11 Correct 175 ms 22832 KB Output is correct
12 Correct 178 ms 21140 KB Output is correct
13 Correct 165 ms 20448 KB Output is correct
14 Correct 214 ms 16672 KB Output is correct
15 Correct 205 ms 18124 KB Output is correct
16 Correct 1 ms 852 KB Output is correct
17 Correct 1 ms 724 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 2 ms 468 KB Output is correct
20 Correct 493 ms 167660 KB Output is correct
21 Correct 543 ms 151528 KB Output is correct
22 Correct 506 ms 89140 KB Output is correct
23 Correct 1199 ms 34940 KB Output is correct
24 Correct 213 ms 9916 KB Output is correct
25 Correct 221 ms 10756 KB Output is correct
26 Correct 253 ms 10852 KB Output is correct
27 Correct 377 ms 33604 KB Output is correct
28 Correct 1126 ms 34964 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Incorrect 1 ms 596 KB Output isn't correct
31 Halted 0 ms 0 KB -