Submission #568950

#	Time	Username	Problem	Language	Result	Execution time	Memory
568950		HappyPacMan	Bridges (APIO19_bridges)	C++14	16 / 100	689 ms	3780 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e4 + 2;
const int inf = 1e9;
int seg[4*maxn];

void upd(int i,int l,int r,int u,int v){
	if(l == r){
		seg[i] = v;
	}else{
		int m = (l+r)/2;
		if(u <= m){
			upd(i<<1,l,m,u,v);
		}else{
			upd(i<<1|1,m+1,r,u,v);
		}
		seg[i] = min(seg[i<<1],seg[i<<1|1]);
	}
}
int qry(int i,int l,int r,int ql,int qr){
	if(l > qr || r < ql){
		return inf;
	}else if(ql <= l && r <= qr){
		return seg[i];
	}else{
		int m = (l+r)/2;
		return min(qry(i<<1,l,m,ql,qr),qry(i<<1|1,m+1,r,ql,qr));
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n,m;
	cin >> n >> m;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin >> u >> v >> w;
		upd(1,1,m,i,w);
	}
	int q;
	cin >> q;
	while(q--){
		int t,x,y;
		cin >> t >> x >> y;
		if(t == 1){
			upd(1,1,m,x,y);
		}else{
			int res = 1;
			int li = 1, ri = x;
			while(li < ri){
				int mi = (li+ri)/2;
				if(qry(1,1,m,mi,x-1) >= y){
					ri = mi;
				}else{
					li = mi+1;
				}
			}
			res += x-li;
			int lj = x-1, rj = m;
			while(lj < rj){
				int mj = (lj+rj+1)/2;
				if(qry(1,1,m,x,mj) >= y){
					lj = mj;
				}else{
					rj = mj-1;
				}
			}
			res += lj-x+1;
			cout << res << '\n';
		}
	}
}

• Subtask 1: 0 / 13
• Subtask 2: 16 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27