oj.uz

Submission #736832

# Submission time Handle Problem Language Result Execution time Memory
736832 2023-05-06T09:27:41 Z Magikarp4000 Street Lamps (APIO19_street_lamps) C++17
20 / 100
 305 ms 12716 KB 
#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n' 
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define in(v,x) (v.find(x) != v.end())
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;

const int MAXN = 3e5+1;
int n,q;
string S;
int w[MAXN], old[MAXN], cnt[MAXN];
pair<bool,PII> qrs[MAXN];
int st[MAXN*4];

void update(int s, int tl, int tr, int idx, int val) {
    if (tl == tr) st[s] = val;
    else {
        int tm = (tl+tr)/2;
        if (idx <= tm) update(s*2,tl,tm,idx,val);
        else update(s*2+1,tm+1,tr,idx,val);
        st[s] = max(st[s*2], st[s*2+1]);
    }
}

int query(int s, int tl, int tr, int l, int r) {
    if (l <= tl && r >= tr) return st[s];
    else {
        int tm = (tl+tr)/2;
        int cur = -INF;
        if (l <= tm) cur = max(cur,query(s*2,tl,tm,l,r));
        if (r > tm) cur = max(cur,query(s*2+1,tm+1,tr,l,r));
        return cur;
    }
}

signed main() {
    OPTM;
    cin >> n >> q >> S;
    FOR(i,0,n) {
        if (S[i] == '1') update(1,0,n-1,i,-1);
        else update(1,0,n-1,i,INF);
    }
    FOR(i,0,q) {
        string t; cin >> t;
        if (t == "toggle") {
            int x; cin >> x;
            x--;
            update(1,0,n-1,x,i);
        }
        else {
            int a,b; cin >> a >> b;
            a--; b--;
            int res = query(1,0,n-1,a,b-1);
            cout << max(0,i-res) << ln;
        }
    }
}

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 79 ms 3928 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 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 177 ms 8748 KB Output is correct
6 Correct 217 ms 8916 KB Output is correct
7 Correct 305 ms 9120 KB Output is correct
8 Correct 295 ms 12716 KB Output is correct
9 Correct 97 ms 3920 KB Output is correct
10 Correct 100 ms 4232 KB Output is correct
11 Correct 98 ms 4460 KB Output is correct
12 Correct 257 ms 11272 KB Output is correct
13 Correct 272 ms 12704 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 264 KB Output is correct
2 Incorrect 1 ms 340 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 212 KB Output isn't correct
2 Halted 0 ms 0 KB -