oj.uz

Submission #736457

# Submission time Handle Problem Language Result Execution time Memory
736457 2023-05-05T16:57:41 Z Dan4Life Street Lamps (APIO19_street_lamps) C++17
20 / 100
 256 ms 10996 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxN = (int)3e5+10;

string s;
int n, q, segTree[2*mxN];

void upd(int x, int v, int p=0, int l=1, int r=n){
	if(l==r){ segTree[p]=v; return; }
	int mid = (l+r)>>1; int rp = p+2*(mid-l+1);
	if(x<=mid) upd(x,v,p+1,l,mid);
	else upd(x,v,rp,mid+1,r);
	segTree[p] = max(segTree[p+1],segTree[rp]);
}

int query(int i, int j, int p=0, int l=1, int r=n){
	if(i>r or j<l or i>j) return 0;
	if(i<=l and r<=j) return segTree[p];
	int mid = (l+r)>>1; int rp = p+2*(mid-l+1);
	return max(query(i,j,p+1,l,mid),query(i,j,rp,mid+1,r));
}

int32_t main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> q >> s;
	fill(segTree,segTree+mxN*2,mxN);
	for(int i = 0; i < n; i++) upd(i+1,(s[i]=='1')?0:mxN);
	for(int i = 1; i <= q; i++){
		int x, y; cin >> s >> x;
		if(s[0]=='t') upd(x,i);
		else cin >> y, y--, cout << (query(x,y)!=mxN)*(i-query(x,y)) << "\n";
	}
}

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 3508 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 2668 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 130 ms 7416 KB Output is correct
6 Correct 172 ms 8000 KB Output is correct
7 Correct 202 ms 8704 KB Output is correct
8 Correct 250 ms 10960 KB Output is correct
9 Correct 85 ms 6316 KB Output is correct
10 Correct 97 ms 6600 KB Output is correct
11 Correct 90 ms 6836 KB Output is correct
12 Correct 256 ms 9608 KB Output is correct
13 Correct 242 ms 10996 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

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