Submission #277974

#	Time	Username	Problem	Language	Result	Execution time	Memory
277974		groeneprof	Bridges (APIO19_bridges)	C++14	16 / 100	1189 ms	6404 KiB

bridges

#include <bits/stdc++.h>

#define P(a) do{if(debug) cout<<a<<endl;} while(false)
#define H(a) P(#a<<": "<<a)
#define FR(i,a,b) for(int i = (a); i<(b); i++)
#define F(i,n) FR(i,0,n)

const int debug = 0;
const int inf = 2e9;
using namespace std;

vector<int> st;
int n, m,q;
vector<pair<int,int> > edges;
vector<int> weights;

int update(int i, int v, int u, int L, int R){
	H(i);
	H(v);
	H(u);
	H(L);
	H(R);
	if(L>i || R < i) {P("out of bounds"); return st[u];}
	if(L==R){P("leaf found"); return st[u] = v;}
	st[u] = min(update(i,v,u*2+1,L,(L+R)/2),update(i,v,u*2+2,(L+R)/2+1,R));
	H(i);
	H(v);
	H(u);
	H(L);
	H(R);
	H(st[u]);
	return st[u];
}

int query(int i, int j, int u, int L, int R){
	if(j<L||R<i) return inf;
	if(L>=i && R<=j) return st[u];
	return min(query(i,j,u*2+1,L,(L+R)/2),query(i,j,u*2+2,(L+R)/2+1,R));
}

int bs1(int w, int i){
	int ans = -1;
	for(int bit = 1<<20; bit>0; bit/=2){
		H(ans+bit);
		if(ans+bit<n) H(query(ans+bit,i-1,0,0,n-1));
		if(ans+bit<i&&query(ans+bit,i-1,0,0,n-1)<w){
			ans+=bit;
		}
	}
	return ans+1;
}

int bs2(int w, int i){
	int ans = i-1;
	for(int bit = 1<<20; bit>0; bit/=2){
		H(ans+bit);
		if(ans+bit<n) H(query(i,ans+bit,0,0,n-1));
		if(ans+bit<n-1&&query(i,ans+bit,0,0,n-1)>=w){
			ans+=bit;
		}
	}
	return ans+1;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	edges.resize(m);
	weights.resize(m);
	st.resize(4*n,inf);
	F(i,m){
		cin>>edges[i].first>>edges[i].second>>weights[i];
		edges[i].first--;
		edges[i].second--;
		update(i,weights[i],0,0,n-1);

	}
	/*for(int i : st){
		cout<<i<<" ";
	}
	cout<<endl;*/
	cin>>q;
	F(i,q){
		int type;
		cin>>type;
		if(type==1){
			int a, b;
			cin>>a>>b;
			a--;
			update(a,b,0,0,n-1);
			weights[a] = b;
			/*for(int aa : st){
				cout<<aa<<" ";
			}
			cout<<endl;*/
			
		}
		else{
			int a, b;
			cin>>a>>b;
			a--;
			cout<<bs2(b,a)-bs1(b,a)+1<<endl;
		}
	}
	return 0;
}

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