Submission #597542

#TimeUsernameProblemLanguageResultExecution timeMemory
597542WongChun1234Bridges (APIO19_bridges)C++14
0 / 100
715 ms524288 KiB
#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); } 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; } 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"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...