Submission #432909

#	Time	Username	Problem	Language	Result	Execution time	Memory
432909		TLP39	Bridges (APIO19_bridges)	C++14	16 / 100	900 ms	524292 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pll;

int n,m,q;
int seg[200012]={};
int a[50003];
void build(int v,int st,int ed)
{
    if(st==ed)
    {
        seg[v]=a[st];
        return;
    }
    int mid=(st+ed)>>1;
    build(v<<1,st,mid);
    build(1+(v<<1),mid+1,ed);
    seg[v]=min(seg[v<<1],seg[1+(v<<1)]);
}

void upd(int v,int l,int r,int pos,int val)
{
    if(l==r)
    {
        seg[v]=val;
        return;
    }
    int mid=(l+r)>>1;
    if(mid>=pos) upd(v<<1,l,mid,pos,val);
    else upd(1+(v<<1),mid+1,r,pos,val);
    seg[v]=min(seg[v<<1],seg[1+(v<<1)]);
}

int que(int v,int l,int r,int st,int ed)
{
    if(st>ed) return 1000000001;
    if(l==st && r==ed) return seg[v];
    int mid=(l+r)>>1;
    return min(que(v<<1,l,mid,st,min(mid,ed)),que(1+(v<<1),mid+1,r,max(mid+1,st),ed));
}


int getlow(int x,int w)
{
    if(x==1) return 1;
    int hi=x,low=1,av;
    while(hi>low)
    {
        av=(hi+low)>>1;
        if(que(1,1,m,av,x-1)>=w) hi=av;
        else low=av+1;
    }
    return hi;
}

int gethi(int x,int w)
{
    if(x==n) return n;
    int low=x,hi=n,av;
    while(hi>low)
    {
        av=(hi+low+1)>>1;
        if(que(1,1,m,x,av-1)>=w) low=av;
        else hi=av-1;
    }
    return hi;
}

int main()
{
    scanf("%d %d",&n,&m);
    int t1,t2;
    int t,u,v;
    for(int i=1;i<n;i++)
    {
        scanf("%d %d %d",&t1,&t2,&a[i]);
    }
    if(n==1)
    {
        scanf("%d",&q);
        while(q--)
        {
            scanf("%d %d %d",&t,&u,&v);
            if(t==2) printf("1\n");
        }
        return 0;
    }
    build(1,1,m);
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d %d %d",&t,&u,&v);
        if(t==1)
        {
            upd(1,1,m,u,v);
        }
        else
        {
            printf("%d\n",gethi(u,v)-getlow(u,v)+1);
        }
    }
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
bridges.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         scanf("%d %d %d",&t1,&t2,&a[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         scanf("%d",&q);
      |         ~~~~~^~~~~~~~~
bridges.cpp:84:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |             scanf("%d %d %d",&t,&u,&v);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~
bridges.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
bridges.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         scanf("%d %d %d",&t,&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

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