oj.uz

Submission #597545

# Submission time Handle Problem Language Result Execution time Memory
597545 2022-07-16T09:47:19 Z WongChun1234 Bridges (APIO19_bridges) C++14
16 / 100
 799 ms 9460 KB 
#include<bits/stdc++.h>
using namespace std;
const int N=150050;
int n,m,q,u[N],v[N],w[N],ans,t,a,b,seg[N<<2];
bool vis[N];
vector<int> adj[N];
void build(int id,int l,int r){
	if (l==r){
		seg[id]=w[l];
		return;
	}
	int mid=(l+r)/2;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	seg[id]=min(seg[id*2],seg[id*2+1]);
}
void modify(int id,int l,int r,int ql,int val){
	if (l>ql||r<ql) return;
	if (l==r){
		seg[id]=val;
		return;
	}
	int mid=(l+r)/2;
	modify(id*2,l,mid,ql,val);
	modify(id*2+1,mid+1,r,ql,val);
	seg[id]=min(seg[id*2],seg[id*2+1]);
}
int query(int id,int l,int r,int ql,int qr){
	if (l>qr||r<ql) return INT_MAX;
	if (l>=ql&&r<=qr) return seg[id];
	int mid=(l+r)/2;
	return min(query(id*2,l,mid,ql,qr),query(id*2+1,mid+1,r,ql,qr));
}
int main(){
	cin>>n>>m;
	for (int i=1;i<=m;i++){
		cin>>u[i]>>v[i]>>w[i];
		adj[u[i]].push_back(i);
		adj[v[i]].push_back(-i);
	}
	if (m) build(1,1,m);
	cin>>q;
	while (q--){
		cin>>t>>a>>b;
		if (t==1){
			w[a]=b;
			modify(1,1,m,a,b);
			continue;
		}
		if (!m){
			cout<<"1\n";
			continue;
		}
		int ll,rr,mm,currl;
		ll=1,rr=a-1;
		if (w[a-1]<b){
			currl=a;
			goto skip;
		}
		while (ll<rr){
			mm=(ll+rr)/2;
			if (query(1,1,m,mm,a-1)>=b) rr=mm;
			else ll=mm+1;
		}
		currl=rr;
		skip:;
		ll=a,rr=m;
		if (w[a]<b){
			cout<<a-currl+1<<"\n";
			continue;
		}
		while (ll<rr){
			mm=(ll+rr+1)/2;
			if (query(1,1,m,a,mm)>=b) ll=mm;
			else rr=mm-1;
		}
		cout<<ll-currl+2<<"\n";
	}
}

Subtask #1
0 / 13.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 6592 KB Output is correct
2 Correct 331 ms 6516 KB Output is correct
3 Correct 331 ms 6748 KB Output is correct
4 Correct 332 ms 6608 KB Output is correct
5 Correct 340 ms 6688 KB Output is correct
6 Correct 495 ms 6960 KB Output is correct
7 Correct 501 ms 6764 KB Output is correct
8 Correct 508 ms 6856 KB Output is correct
9 Correct 180 ms 5324 KB Output is correct
10 Correct 388 ms 8452 KB Output is correct
11 Correct 365 ms 8248 KB Output is correct
12 Correct 799 ms 9460 KB Output is correct
13 Correct 214 ms 9184 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 6592 KB Output is correct
2 Correct 331 ms 6516 KB Output is correct
3 Correct 331 ms 6748 KB Output is correct
4 Correct 332 ms 6608 KB Output is correct
5 Correct 340 ms 6688 KB Output is correct
6 Correct 495 ms 6960 KB Output is correct
7 Correct 501 ms 6764 KB Output is correct
8 Correct 508 ms 6856 KB Output is correct
9 Correct 180 ms 5324 KB Output is correct
10 Correct 388 ms 8452 KB Output is correct
11 Correct 365 ms 8248 KB Output is correct
12 Correct 799 ms 9460 KB Output is correct
13 Correct 214 ms 9184 KB Output is correct
14 Incorrect 340 ms 5508 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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