Submission #281979

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
281979	2020-08-23T18:17:01 Z	Revo7	Deda (COCI17_deda)	C++14	100 / 140	1000 ms	4216 KB

deda

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define left 2*i+1
#define righ 2*i+2
#define mid (l+r)/2
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
const int maxn=2e5+100;
const int mod=1e9+9;
const int base=27;
const int inf =1e9+10;

int n,q;
int st[4*maxn];
struct player{
    int val,cnt,id;
};
vector<player>a;
bool com(player a,player b){
    if(a.val==b.val){
        if(a.cnt==b.cnt)return a.id>b.id;
        return a.cnt<b.cnt;
    }
    return a.val<b.val;
}

void build(int i,int l,int r){
    if(l==r){
        st[i]=inf;
        return;
    }
    build(left,l,mid);
    build(righ,mid+1,r);
    st[i]=inf;
}

void upd(int i,int l,int r,int id,int val){
    if(r<id||l>id)return ;
    if(l==r){
        st[i]=val;
        return ;
    }
    upd(left,l,mid,id,val);
    upd(righ,mid+1,r,id,val);
    st[i]=min(st[left],st[righ]);
}
int qur(int i,int l,int r,int ql,int qr){
    if(r<ql||l>qr)return inf;
    if(l>=ql&&r<=qr)return st[i];
    return min(qur(left,l,mid,ql,qr),qur(righ,mid+1,r,ql,qr));
}
bool check(int l,int r,int val){
    return qur(0,0,n-1,l,r)<=val;
}
int bs(int b,int val){
    int l=b,r=n-1,ans=-2;
    while(l<=r){
        if(check(b,mid,val)){
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    return ans;
}
int main()
{
    //setIO("threesum");
    //IOS
    //cin>>n>>q;
    scanf("%d%d",&n,&q);
    build(0,0,n-1);
    while(q--){
        char t;
        //cin>>t;
        scanf("%c",&t);
        scanf("%c",&t);
        //cout<<t<<endl;
        if(t=='M'){
            int x,a;
            //cin>>x>>a;
            scanf("%d%d",&x,&a);
            upd(0,0,n-1,a-1,x);
        }
        else{
            int y,b;
            //cin>>y>>b;
            scanf("%d%d",&y,&b);
            printf("%d\n",bs(b-1,y)+1);
        }
    }
    return 0;
}

Compilation message

deda.cpp: In function 'int main()':
deda.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   73 |     scanf("%d%d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~
deda.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   78 |         scanf("%c",&t);
      |         ~~~~~^~~~~~~~~
deda.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   79 |         scanf("%c",&t);
      |         ~~~~~^~~~~~~~~
deda.cpp:84:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |             scanf("%d%d",&x,&a);
      |             ~~~~~^~~~~~~~~~~~~~
deda.cpp:90:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   90 |             scanf("%d%d",&y,&b);
      |             ~~~~~^~~~~~~~~~~~~~

Subtask #1

100.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	256 KB	Output is correct
2	Correct	1 ms	256 KB	Output is correct
3	Correct	8 ms	384 KB	Output is correct
4	Execution timed out	1095 ms	4216 KB	Time limit exceeded
5	Correct	804 ms	2428 KB	Output is correct
6	Correct	988 ms	3800 KB	Output is correct
7	Execution timed out	1086 ms	4096 KB	Time limit exceeded