Submission #1281338

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281338		Faisal_Saqib	Bridges (APIO19_bridges)	C++20	16 / 100	714 ms	2584 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+10,X=(1<<18);
// int par[N],sz[N],ans[N];
// int get(int x)
// {
//     return (par[x]==x?x:par[x]=get(par[x]));
// }
// void join(int x,int y)
// {
//     x=get(x);
//     y=get(y);
//     if(x==y)return;
//     sz[x]+=sz[y];
//     par[y]=x;
// }
// vector<pair<ll,ll>> ma[N];
// bool vis[N];
// ll w[N];
// ll sz=0,cw=0;
// void dfs(int x,int p=-1)
// {
//     vis[x]=1;
//     sz++;
//     for(auto sza:ma[x])
//     {
//         int y=sza.second,i=sza.first;
//         if(y==p or vis[y])continue;
//         if(w[i]>=cw)
//         {
//             dfs(y,x);
//         }
//     }
// }
int seg[(1<<19)+2];
void Set(int i,int w)
{
    seg[i+X]=w;
    // cout<<i+X<<' ';
    for(i=(i+X)>>1;i>0;i>>=1)
    {
        // cout<<i<<' ';
        seg[i]=min(seg[2*i],seg[2*i+1]);
    }
    // cout<<endl;
}
int getmin(int ql,int qr,int l=0,int r=X-1,int v=1)
{
    if(r<ql or qr<l)
        return 1e9+10;
    if(ql<=l and r<=qr)
    {
        return seg[v];
    }
    int mid=(l+r)>>1;
    return min(getmin(ql,qr,l,mid,2*v),getmin(ql,qr,mid+1,r,2*v+1));
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int x,y,w;
        cin>>x>>y>>w;
        Set(i,w);
    }
    int q;
    cin>>q;
    for(int i=0;i<q;i++)
    {
        int t;
        cin>>t;
        ll s,wq;
        cin>>s>>wq;
        s--;
        if(t==1)
        {
            Set(s,wq);
        }
        else
        {
            ll l=s-1,r=m;
            while(l+1<r)
            {
                ll mid=(l+r)/2;
                if(getmin(s,mid)>=wq)
                {
                    l=mid;
                }
                else
                {
                    r=mid;
                }
            }
            ll cur=(l-s+2);
            l=-1,r=s;
            while(l+1<r)
            {
                ll mid=(l+r)/2;
                if(getmin(mid,s-1)>=wq)
                {
                    r=mid;
                }
                else
                {
                    l=mid;
                }
            }
            cout<<cur+(s-r)<<endl;
            //[s,l+1]
        }

        // edg.push_back({w,-1,i,s});
    }
    // sort(rbegin(edg),rend(edg));
    // for(auto ty:edg)
    // {
    //     if(ty[1]==-1)
    //     {
    //         // query
    //         ans[ty[2]]=sz[get(ty[3])];
    //     }
    //     else
    //     {
    //         // edge
    //         join(ty[1],ty[2]);
    //     }
    // }
    // for(int i=0;i<q;i++)
    // {
    //     cout<<ans[i]<<' ';
    // }
    // cout<<endl;
}

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