Submission #281975

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
281975	2020-08-23T18:08:50 Z	Revo7	Deda (COCI17_deda)	C++14	60 / 140	1000 ms	6520 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 ll maxn=2e5+100;
const ll mod=1e9+9;
const ll base=27;
const ll inf =1e9+10;

ll n,q;
int st[4*maxn];
struct player{
    ll 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;
}

ll pl[6][maxn];
struct sub{
    ll tim,x,y;
};

bool cmp(sub a,sub b){
    return a.tim<b.tim;
}
vector<sub>s;
bool flag[maxn],sw[6][maxn];
int in[maxn];

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;
    build(0,0,n-1);
    while(q--){
        char t;
        cin>>t;
        if(t=='M'){
            int x,a;
            cin>>x>>a;
            upd(0,0,n-1,a-1,x);
        }
        else{
            int y,b;
            cin>>y>>b;
            cout<<bs(b-1,y)+1<<endl;
        }
    }
    return 0;
}

Subtask #1

60.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	16 ms	512 KB	Output is correct
4	Execution timed out	1067 ms	5332 KB	Time limit exceeded
5	Execution timed out	1082 ms	5432 KB	Time limit exceeded
6	Execution timed out	1067 ms	6520 KB	Time limit exceeded
7	Execution timed out	1069 ms	6212 KB	Time limit exceeded