Submission #529851

#	Time	Username	Problem	Language	Result	Execution time	Memory
529851		ammar2000	Bridges (APIO19_bridges)	C++17	16 / 100	323 ms	5756 KiB

bridges

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define F first
#define S second
#define coy cout<<"YES\n"
#define con cout<<"NO\n"
#define co1 cout<<"-1\n"
#define sc(x) scanf("%lld",&x)
#define all(x) x.begin(),x.end()
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int SI=4e5+7;
ll INF=8e18+7;
int dx[] = {1 , -1 , 0 , 0};
int dy[] = {0 , 0 , 1 , -1};
int MOD=1e9+7;
ll n,m,a[SI],st[SI],RQ,LQ;
void build(int x,int l,int r)
{
    if (l==r)
    {
        st[x]=a[l];
        return ;
    }
    ll m=(l+r)/2;
    build (2*x,l,m);
    build (2*x+1,m+1,r);
    st[x]=min(st[2*x],st[2*x+1]);
}
void update(int x,int l,int r,int in)
{
    if (l==r)
    {
        st[x]=a[l];
        return ;
    }
    ll m=(l+r)/2;
    if (in<=m)
        update(2*x,l,m,in);
    else update (2*x+1,m+1,r,in);
    st[x]=min(st[2*x],st[2*x+1]);
}
void rq(int x,int l,int r,int ql,int v)
{
    if (r<ql)
        return ;
    if (l==r)
    {
        if (st[x]<v)
            RQ=l;
        return ;
    }
    ll m=(l+r)/2;
    if (ql>m)
    {
        if (st[2*x+1]>=v)
            return ;
        else rq(2*x+1,m+1,r,ql,v);
    }
    if (RQ)
        return ;
    //cout <<st[2*x]<<"\n";
    if (st[2*x]<v)
      rq (2*x,l,m,ql,v);
    if (RQ)
        return ;
    rq(2*x+1,m+1,r,ql,v);
}
void lq (int x,int l,int r,int qr ,ll v)
{
    if (l>qr)
        return;
    if (l==r)
    {
        if (st[x]<v)
        LQ=l;
        return ;
    }
    ll m=(l+r)/2;
    if (qr<m+1)
    {
        if (st[2*x]>=v)
            return ;
        lq(2*x,l,m,qr,v);
    }
    if(LQ)
        return ;
    if (st[2*x+1]<v)
        lq(2*x+1,m+1,r,qr,v);
    if (LQ)
        return ;
    lq(2*x,l,m,qr,v);
}
int main()
{
   //fast
   cin>>n>>m;
   for (int i=1;i<=m;i++)
   {
       ll e;
       cin>>e>>e>>e;
       a[i]=e;
   }
   swap(m,n);
   ll N=1;
   while (N<n)
    N*=2;
   build (1,1,N);
   ll q;
   cin>>q;
   while (q--)
   {
       ll t,x,y;
       cin>>t>>x>>y;
       if (t==1)
        {a[x]=y;
        update (1,1,N,x);
        continue ;}
        RQ=LQ=0;
        rq(1,1,N,x,y);
        if (RQ==0)
            RQ=n+1;
        if (x>1)
        lq(1,1,N,x-1,y);
         cout <<RQ-LQ<<"\n";
   }
   // use scanf not cin
   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