Submission #379146

#	Time	Username	Problem	Language	Result	Execution time	Memory
379146		FatihSolak	Deda (COCI17_deda)	C++17	80 / 140	1090 ms	5584 KiB

deda

#include <bits/stdc++.h>
#define N 200005
#define K 20
#define INF 1000000005
using namespace std;
int t[4*N];
void upd(int v,int l,int r,int pos,int val){
    if(l == r){
        t[v] = val;
        return;
    }
    int m = (l+r)/2;
    if(pos<=m){
        upd(v*2,l,m,pos,val);
    }
    else{
        upd(v*2+1,m+1,r,pos,val);
    }
    t[v] = min(t[v*2],t[v*2+1]);
}
int get(int v,int tl,int tr,int l,int r){
    if(tr < l || r < tl)return INF;
    if(l <= tl && tr <= r){
        return t[v];
    }
    int tm = (tl+tr)/2;
    return min(get(v*2,tl,tm,l,r),get(v*2+1,tm+1,tr,l,r));
}
void solve(){
    int n,q;
    scanf("%d %d ",&n,&q);
    for(int i=0;i<4*N;i++)t[i] = INF;
    for(int i=0;i<q;i++){
        char a;
        int b,c;
        scanf(" %c%d%d",&a,&b,&c);
        //cout << a << " " << b << " " << c << endl;
        if(a == 'M'){
            upd(1,1,n,c,b);
        }
        if(a == 'D'){
            int l = c, r=n;
            while(l < r){
                int m = (l+r)/2;
                if(get(1,1,n,c,m) > b){
                    l = m+1;
                }
                else r = m;
            }
            if(get(1,1,n,c,l) > b){
                 printf("-1\n");
            }
            else printf("%d\n",l);
           //cout << (get(1,1,n,c,l) > b ? -1 : l) << endl;
        }
    }
}

int main(){
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Compilation message (stderr)

deda.cpp: In function 'void solve()':
deda.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |     scanf("%d %d ",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~
deda.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   36 |         scanf(" %c%d%d",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 80 / 140