oj.uz

답안 #736457

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
736457 2023-05-05T16:57:41 Z Dan4Life 가로등 (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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 73 ms 3508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -