oj.uz

Submission #530756

# Submission time Handle Problem Language Result Execution time Memory
530756 2022-02-26T17:02:51 Z A_D Bridges (APIO19_bridges) C++14
16 / 100
 689 ms 6584 KB 
#include <bits/stdc++.h>

#define int long long
#define ii pair<int,int>
#define F first
#define S second

using namespace std;
const int N=1e5+100;
vector<int> g[N];
int seg[4*N];
void update(int p,int s,int e,int i,int v)
{
    if(s==e){
        seg[p]=v;
        return;
    }
    int mid=(s+e)/2;
    if(i<=mid){
        update(p*2,s,mid,i,v);
    }
    else{
        update(p*2+1,mid+1,e,i,v);
    }
    seg[p]=min(seg[p*2],seg[p*2+1]);
}
int get(int p,int s,int e,int a,int b)
{
    if(a<=s&&e<=b){
        return seg[p];
    }
    if(s>b||e<a)return 1e18;
    int mid=(s+e)/2;
    return min(get(p*2,s,mid,a,b),get(p*2+1,mid+1,e,a,b));
}
void solve()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<n;i++){
        int b;
        scanf("%lld",&b);
        scanf("%lld",&b);
        scanf("%lld",&b);
        update(1,1,n,i,b);
    }
    int q;
    cin>>q;
    while(q--){
        int t;
        scanf("%lld",&t);
        if(t==1){
            int b,w;
            scanf("%lld",&b);
            scanf("%lld",&w);
            update(1,1,n,b,w);
        }
        else{
            int b,w;
            scanf("%lld",&b);
            scanf("%lld",&w);
            int ans=1;
            if(b!=1){
                int l=1,r=b-1,ann=b;
                while(l<=r){
                    int mid=(l+r)/2;
                    if(get(1,1,n,mid,b-1)>=w){
                        ann=mid;
                        r=mid-1;
                    }
                    else{
                        l=mid+1;
                    }
                }
                ans+=b-ann;
            }
            if(b!=n){
                int l=b,r=n-1,ann=b;
                while(l<=r){
                    int mid=(l+r)/2;
                    if(get(1,1,n,b,mid)>=w){
                        ann=mid+1;
                        l=mid+1;
                    }
                    else{
                        r=mid-1;
                    }
                }
                ans+=ann-b;
            }
            printf("%lld\n",ans);
        }
    }
}
main()
{
    int t=1;
//    cin>>t;
    while(t--){
        solve();
    }
}

Compilation message

bridges.cpp:95:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   95 | main()
      | ^~~~
bridges.cpp: In function 'void solve()':
bridges.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         scanf("%lld",&b);
      |         ~~~~~^~~~~~~~~~~
bridges.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         scanf("%lld",&b);
      |         ~~~~~^~~~~~~~~~~
bridges.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         scanf("%lld",&b);
      |         ~~~~~^~~~~~~~~~~
bridges.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         scanf("%lld",&t);
      |         ~~~~~^~~~~~~~~~~
bridges.cpp:54:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |             scanf("%lld",&b);
      |             ~~~~~^~~~~~~~~~~
bridges.cpp:55:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |             scanf("%lld",&w);
      |             ~~~~~^~~~~~~~~~~
bridges.cpp:60:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |             scanf("%lld",&b);
      |             ~~~~~^~~~~~~~~~~
bridges.cpp:61:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |             scanf("%lld",&w);
      |             ~~~~~^~~~~~~~~~~

Subtask #1
0 / 13.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 3700 KB Output is correct
2 Correct 401 ms 6548 KB Output is correct
3 Correct 373 ms 6416 KB Output is correct
4 Correct 384 ms 6472 KB Output is correct
5 Correct 417 ms 6492 KB Output is correct
6 Correct 415 ms 6520 KB Output is correct
7 Correct 392 ms 6488 KB Output is correct
8 Correct 448 ms 6460 KB Output is correct
9 Correct 36 ms 4172 KB Output is correct
10 Correct 388 ms 5392 KB Output is correct
11 Correct 418 ms 5492 KB Output is correct
12 Correct 689 ms 6584 KB Output is correct
13 Correct 134 ms 6340 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 3700 KB Output is correct
2 Correct 401 ms 6548 KB Output is correct
3 Correct 373 ms 6416 KB Output is correct
4 Correct 384 ms 6472 KB Output is correct
5 Correct 417 ms 6492 KB Output is correct
6 Correct 415 ms 6520 KB Output is correct
7 Correct 392 ms 6488 KB Output is correct
8 Correct 448 ms 6460 KB Output is correct
9 Correct 36 ms 4172 KB Output is correct
10 Correct 388 ms 5392 KB Output is correct
11 Correct 418 ms 5492 KB Output is correct
12 Correct 689 ms 6584 KB Output is correct
13 Correct 134 ms 6340 KB Output is correct
14 Incorrect 330 ms 3228 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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