oj.uz

답안 #262748

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
262748 2020-08-13T08:10:02 Z dsjong 다리 (APIO19_bridges) C++14
16 / 100
 925 ms 4132 KB 
#include <bits/stdc++.h>
using namespace std;
int a[50005], seg[200005];
void build(int L, int R, int node){
	if(L==R){
		seg[node]=a[L];
		return;
	}
	int M=(L+R)/2;
	build(L, M, 2*node);
	build(M+1, R, 2*node+1);
	seg[node]=min(seg[2*node], seg[2*node+1]);
}
int query(int a, int b, int L, int R, int node){
	if(a>b) return 1e9;
	if(b<L || a>R) return 1e9;
	if(a<=L && R<=b) return seg[node];
	int M=(L+R)/2;
	return min(query(a, b, L, M, 2*node), query(a, b, M+1, R, 2*node+1));
}
void update(int a, int v, int L, int R, int node){
	if(a<L || a>R) return;
	if(L==R){
		seg[node]=v;
		return;
	}
	int M=(L+R)/2;
	update(a, v, L, M, 2*node);
	update(a, v, M+1, R, 2*node+1);
	seg[node]=min(seg[2*node], seg[2*node+1]);
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, m;
	cin>>n>>m;
	for(int i=1;i<n;i++){
		int u, v;
		cin>>u>>v>>a[i];
	}
	build(1, n, 1);
	int q;
	cin>>q;
	while(q--){
		int t, x, y;
		cin>>t>>x>>y;
		if(t==1){
			update(x, y, 1, n, 1);
		}
		else{
			int ans1, ans2;
			int L=x-1, R=n-1;
			while(L<R){
				int M=(L+R+1)/2;
				if(query(x, M, 1, n, 1) < y) R=M-1;
				else L=M;
			}
			ans1=L;
			L=1, R=x;
			while(L<R){
				int M=(L+R)/2;
				if(query(M, x-1, 1, n, 1) < y) L=M+1;
				else R=M;
			}
			ans2=L;
			cout<<ans1-ans2+2<<"\n";
		}
	}
}

Subtask #1
0 / 13.0

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

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 500 ms 1272 KB Output is correct
2 Correct 487 ms 3960 KB Output is correct
3 Correct 484 ms 3960 KB Output is correct
4 Correct 511 ms 4064 KB Output is correct
5 Correct 482 ms 4088 KB Output is correct
6 Correct 564 ms 3832 KB Output is correct
7 Correct 547 ms 4044 KB Output is correct
8 Correct 545 ms 4132 KB Output is correct
9 Correct 32 ms 1920 KB Output is correct
10 Correct 503 ms 2936 KB Output is correct
11 Correct 497 ms 2936 KB Output is correct
12 Correct 925 ms 4124 KB Output is correct
13 Correct 163 ms 3832 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 500 ms 1272 KB Output is correct
2 Correct 487 ms 3960 KB Output is correct
3 Correct 484 ms 3960 KB Output is correct
4 Correct 511 ms 4064 KB Output is correct
5 Correct 482 ms 4088 KB Output is correct
6 Correct 564 ms 3832 KB Output is correct
7 Correct 547 ms 4044 KB Output is correct
8 Correct 545 ms 4132 KB Output is correct
9 Correct 32 ms 1920 KB Output is correct
10 Correct 503 ms 2936 KB Output is correct
11 Correct 497 ms 2936 KB Output is correct
12 Correct 925 ms 4124 KB Output is correct
13 Correct 163 ms 3832 KB Output is correct
14 Incorrect 427 ms 888 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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