oj.uz

Submission #893528

# Submission time Handle Problem Language Result Execution time Memory
893528 2023-12-27T06:23:33 Z Warinchai Bridges (APIO19_bridges) C++14
16 / 100
 691 ms 8028 KB 
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int> >v[100005];
int w[100005];
int vis[100005];
struct segtree{
    int info[400005];
    void upd(int st,int en,int i,int pos,int val){
        if(st>pos||en<pos)return;
        if(st==en)return void(info[i]=val);
        int m=(st+en)/2;
        upd(st,m,i*2,pos,val);
        upd(m+1,en,i*2+1,pos,val);
        info[i]=min(info[i*2],info[i*2+1]);
    }
    int fmin(int st,int en,int i,int l,int r){
        if(st>r||en<l)return INT_MAX;
        if(st>=l&&en<=r)return info[i];
        int m=(st+en)/2;
        return min(fmin(st,m,i*2,l,r),fmin(m+1,en,i*2+1,l,r));
    }
}tr;
/*int dfs(int x,int wc){
    vis[x]=1;
    int sz=1;
    for(auto e:v[x]){
        if(w[e.second]>=wc&&vis[e.first]==0){
            sz+=dfs(e.first,wc);
        }
    }
    return sz;
}*/
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        tr.upd(1,n,1,i,c);
    }
    int q;
    cin>>q;
    while(q--){
        int t;
        cin>>t;
        if(t==1){
            int x,r;
            cin>>x>>r;
            tr.upd(1,n,1,x,r);
        }else{
            int s,w;
            cin>>s>>w;
            //cout<<dfs(s,w)<<"\n";
            int rans=1;
            int st,en,ans;
            st=1,en=s-1,ans=s;
            while(st<=en){
                int m=(st+en)/2;
                if(tr.fmin(1,n,1,m,s-1)>=w){
                    ans=m;
                    en=m-1;
                }else{
                    st=m+1;
                }
            }
            rans+=s-ans;
            st=s,en=n-1,ans=s-1;
            while(st<=en){
                int m=(st+en)/2;
                if(tr.fmin(1,n,1,s,m)>=w){
                    ans=m;
                    st=m+1;
                }else{
                    en=m-1;
                }
            }
            rans+=ans+1-s;
            cout<<rans<<"\n";
        }
    }
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2908 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 374 ms 5084 KB Output is correct
2 Correct 370 ms 5096 KB Output is correct
3 Correct 375 ms 5456 KB Output is correct
4 Correct 374 ms 5204 KB Output is correct
5 Correct 374 ms 5712 KB Output is correct
6 Correct 383 ms 6384 KB Output is correct
7 Correct 389 ms 7852 KB Output is correct
8 Correct 386 ms 7764 KB Output is correct
9 Correct 165 ms 4420 KB Output is correct
10 Correct 355 ms 6740 KB Output is correct
11 Correct 360 ms 7252 KB Output is correct
12 Correct 609 ms 8028 KB Output is correct
13 Correct 164 ms 8016 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 5084 KB Output is correct
2 Correct 370 ms 5096 KB Output is correct
3 Correct 375 ms 5456 KB Output is correct
4 Correct 374 ms 5204 KB Output is correct
5 Correct 374 ms 5712 KB Output is correct
6 Correct 383 ms 6384 KB Output is correct
7 Correct 389 ms 7852 KB Output is correct
8 Correct 386 ms 7764 KB Output is correct
9 Correct 165 ms 4420 KB Output is correct
10 Correct 355 ms 6740 KB Output is correct
11 Correct 360 ms 7252 KB Output is correct
12 Correct 609 ms 8028 KB Output is correct
13 Correct 164 ms 8016 KB Output is correct
14 Incorrect 345 ms 5200 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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