이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define PB push_back
#define EB emplace_back
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
#define ll long long
#define sz(x) (int)x.size()
#define TASK "cf"
using namespace std;
const int maxn=1e5+5;
int T[2][4*maxn];
pair<pair<int,int>,int> ds[maxn];
int n,m,q;
void update(int rev,int node,int l,int r,int u,int v,int val) {
if (u>r|| v<l) return ;
if (u<=l&& r<=v) {
T[rev][node]=val; return ;
}
int mid=l+r>>1;
update(rev,node<<1,l,mid,u,v,val);
update(rev,node<<1|1,mid+1,r,u,v,val);
T[rev][node]=min(T[rev][node<<1],T[rev][node<<1|1]);
}
int get(int rev,int node,int l,int r,int u,int v) {
if (u>r||v<l) return 1e9+9;
if (u<=l&&r<=v) return T[rev][node];
int mid=l+r>>1;
return min(get(rev,node<<1,l,mid,u,v),get(rev,node<<1|1,mid+1,r,u,v));
}
int tim1(int pos,int val) {
int lo=1,hi=pos-1;
if (hi<lo || hi<1) return pos;
int res=pos;
while(hi-lo>=0){
int mid=hi+lo>>1;
if (get(0,1,1,n,mid,pos-1)>=val){
res=mid;
hi=mid-1;
}
else lo=mid+1;
}
return res;
}
int tim2(int pos,int val) {
int lo=pos+1,hi=n;
if (hi<lo || lo>n) return pos;
int res=pos;
while(hi-lo>=0){
int mid=hi+lo>>1;
if (get(1,1,1,n,pos+1,mid)>=val){
res=mid;
lo=mid+1;
}
else hi=mid-1;
}
return res;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;
for (int i=1;i<=m;i++) {
int x,y,z;cin>>x>>y>>z;
ds[i]=mp(mp(x,y),z);
}
for (int i=1;i<=m;i++) {
int u=ds[i].fi.fi,v=ds[i].fi.se,w=ds[i].se;
update(0,1,1,n,u,u,w);
update(1,1,1,n,v,v,w);
}
cin>>q;
while(q--) {
int type,x,y; cin>>type>>x>>y;
if (type==1){
int u=ds[x].fi.fi,v=ds[x].fi.se;
ds[x].se=y;
update(0,1,1,n,u,u,y);
update(1,1,1,n,v,v,y);
}
else {
int lo=tim1(x,y),hi=tim2(x,y);
cout<<hi-lo+1<<"\n";
}
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
bridges.cpp: In function 'void update(int, int, int, int, int, int, int)':
bridges.cpp:29:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
29 | int mid=l+r>>1;
| ~^~
bridges.cpp: In function 'int get(int, int, int, int, int, int)':
bridges.cpp:38:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
38 | int mid=l+r>>1;
| ~^~
bridges.cpp: In function 'int tim1(int, int)':
bridges.cpp:47:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
47 | int mid=hi+lo>>1;
| ~~^~~
bridges.cpp: In function 'int tim2(int, int)':
bridges.cpp:62:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
62 | int mid=hi+lo>>1;
| ~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |