oj.uz

Submission #1078256

# Submission time Handle Problem Language Result Execution time Memory
1078256 2024-08-27T14:35:15 Z giaminh2211 Street Lamps (APIO19_street_lamps) C++14
20 / 100
 210 ms 13652 KB 
#include <bits/stdc++.h>

using namespace std;
using ll=long long;

int n, q;
const int N=3e5+13;
int st[N << 2];
char c;
int a[N];
string type;
int x, y;

void update(int id, int l, int r, int i, int val){
    if(l > i || r < i) return;
    if(l==r){
        st[id]=val;
        return;
    }
    int mid=l+r >> 1;
    update(id << 1, l, mid, i, val);
    update(id << 1 | 1, mid+1, r, i, val);
    st[id] = max(st[id << 1], st[id << 1 | 1]);
}

int get(int id, int l, int r, int u, int v){
    if(l > v || r < u) return -1e9;
    if(u<=l && r<=v){
        return st[id];
    }
    int mid=l+r>>1;
    int get1=get(id << 1, l, mid, u, v);
    int get2=get(id << 1 | 1, mid+1, r, u, v);
    return max(get1, get2);
}

void scan(){
    cin >> n >> q;
    for(int i=1; i<=n; i++){
        cin >> c;
        a[i]=c-'0';
        if(a[i]==1) update(1, 1, n, i, 0);
        else update(1, 1, n, i, 1e9);
    }
}

void solve(){
    for(int t=1; t<=q; t++){
        cin >> type >> x;
        if(type=="toggle"){
            a[x] ^= 1;
            update(1, 1, n, x, a[x]);
            if(a[x]==1) update(1, 1, n, x, t);
            else update(1, 1, n, x, 1e9);
        }
        else{
            cin >> y;
            y--;
            int val=get(1, 1, n, x, y);
            if(val <= 1e8) cout << t-val;
            else cout << 0;
            cout << '\n';
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    scan();
    solve();
}

Compilation message

street_lamps.cpp: In function 'void update(int, int, int, int, int)':
street_lamps.cpp:20:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |     int mid=l+r >> 1;
      |             ~^~
street_lamps.cpp: In function 'int get(int, int, int, int, int)':
street_lamps.cpp:31:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |     int mid=l+r>>1;
      |             ~^~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 204 ms 9572 KB Output is correct
6 Correct 205 ms 10604 KB Output is correct
7 Correct 209 ms 11360 KB Output is correct
8 Correct 207 ms 13624 KB Output is correct
9 Correct 60 ms 4120 KB Output is correct
10 Correct 92 ms 4176 KB Output is correct
11 Correct 65 ms 4436 KB Output is correct
12 Correct 210 ms 12112 KB Output is correct
13 Correct 193 ms 13652 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -