oj.uz

Submission #432909

# Submission time Handle Problem Language Result Execution time Memory
432909 2021-06-18T15:04:25 Z TLP39 Bridges (APIO19_bridges) C++14
16 / 100
 900 ms 524292 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 270 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 1204 KB Output is correct
2 Correct 442 ms 988 KB Output is correct
3 Correct 439 ms 1092 KB Output is correct
4 Correct 460 ms 1064 KB Output is correct
5 Correct 438 ms 1092 KB Output is correct
6 Correct 534 ms 1256 KB Output is correct
7 Correct 541 ms 1236 KB Output is correct
8 Correct 511 ms 1348 KB Output is correct
9 Correct 32 ms 1732 KB Output is correct
10 Correct 490 ms 2900 KB Output is correct
11 Correct 464 ms 2768 KB Output is correct
12 Correct 900 ms 3844 KB Output is correct
13 Correct 196 ms 3648 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 22 ms 1852 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 1204 KB Output is correct
2 Correct 442 ms 988 KB Output is correct
3 Correct 439 ms 1092 KB Output is correct
4 Correct 460 ms 1064 KB Output is correct
5 Correct 438 ms 1092 KB Output is correct
6 Correct 534 ms 1256 KB Output is correct
7 Correct 541 ms 1236 KB Output is correct
8 Correct 511 ms 1348 KB Output is correct
9 Correct 32 ms 1732 KB Output is correct
10 Correct 490 ms 2900 KB Output is correct
11 Correct 464 ms 2768 KB Output is correct
12 Correct 900 ms 3844 KB Output is correct
13 Correct 196 ms 3648 KB Output is correct
14 Incorrect 404 ms 780 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 270 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -