Submission #409354

#	Time	Username	Problem	Language	Result	Execution time	Memory
409354		MOUF_MAHMALAT	Bridges (APIO19_bridges)	C++14	16 / 100	1191 ms	4816 KiB

bridges

#include<bits/stdc++.h>
#define all(s) s.begin(),s.end()
using namespace std;
typedef int ll;
ll n,q,t,edg,x,y,z,a[100009],p[400009],id[100009];
void build(ll d,ll l,ll r)
{
    if(l==r)
        return void(p[d]=a[l]);
    ll m=(l+r)/2,i=d*2;
    build(i,l,m),build(i+1,m+1,r);
    p[d]=min(p[i],p[i+1]);
}
void up(ll d,ll l,ll r)
{
    if(l==r)
        return void(p[d]=y);
    ll m=(l+r)/2,i=d*2;
    if(id[x]<=m)
        up(i,l,m);
    else
        up(i+1,m+1,r);
    p[d]=min(p[i],p[i+1]);
}
ll best(ll d,ll l,ll r,ll s,ll e)
{
    if(l>e||r<s)
        return 2e9;
    if(s<=l&&e>=r)
        return p[d];
    ll m=(l+r)/2,i=d*2;
    return min(best(i,l,m,s,e),best(i+1,m+1,r,s,e));
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>edg;
    n=2*n-1;
    for(ll i=1; i<=edg; i++)
    {
        cin>>x>>y>>z;
        if(x>y)
            swap(x,y);
        a[x*2-1]=2e9;
        a[y*2-1]=2e9;
        a[x*2]=z;
        id[i]=x*2;
    }
    build(1,1,n);
    cin>>q;
    while(q--)
    {
        cin>>t>>x>>y;
        if(t==1)
        {
            up(1,1,n);
            continue;
        }
        ll s,e;
        ll l=0,r=x*2-1,m;
        while(r-l>1)
        {
            m=(l+r)/2;
            if(best(1,1,n,m,x*2-1)>=y)
                r=m;
            else
                l=m;
        }
        s=r;
        l=x*2-1,r=n+1;
        while(r-l>1)
        {
            m=(l+r)/2;
            if(best(1,1,n,x*2-1,m)>=y)
                l=m;
            else
                r=m;
        }
        e=l;
        cout<<(e-s)/2+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