Submission #845882

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
845882	2023-09-06T17:20:48 Z	Mr_Ph	Deda (COCI17_deda)	C++14	140 / 140	87 ms	9032 KB

deda

///Never gonna give you up.
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
typedef long long int lli;
typedef unsigned long long ull;
using namespace std;
using namespace __gnu_pbds;
template<class x>
using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;
const ll mod=(ll)1e9+7;
const ll mod1=998244353;
///the defines :)
#define endl '\n'
#define vi vector<int>
#define vll vector<ll>
#define ent(arr) for(int i=0;i<arr.size();i++)cin>>arr[i];
#define all(arr) arr.begin(),arr.end()
#define allr(arr) arr.rbegin(),arr.rend()
#define sz size()
#define int long long
struct segtree
{
    int siz;
    vector<int>vals;
    int neutram_element=0;
    void init(int n)
    {
        siz=1;
        while(siz<n)siz*=2;
        vals.resize(siz*2);
    }
    int merg(int a,int b)
    {
        return min(a,b);
    }
    int single(int a)
    {
        return a;
    }
    void Set(int i,int val,int x,int lx,int rx)
    {
       // cout<<lx<<" "<<rx<<" "<<x<<endl;
        if(lx==rx)
        {
            vals[x]=single(val);
            return;
        }
        int mid=(lx+rx+1)/2;
        if(i<mid)
            Set(i,val,2*x+1,lx,mid-1);
        else Set(i,val,2*x+2,mid,rx);
        vals[x]=merg(vals[2*x+1],vals[2*x+2]);
    }
    void Set(int i,int v)
    {
        Set(i,v,0,0,siz-1);
    }
    int calc(int l,int r,int v,int x,int lx,int rx)
    {
        if(lx>r||rx<l||vals[x]>v)return 1e9+2;
        if(lx==rx)return lx;
        int mid=(lx+rx+1)/2;
       // cout<<lx<<" "<<rx<<" "<<x<<" "<<mid<<endl;
        int e=calc(l,r,v,2*x+1,lx,mid-1);
        if(e==1e9+2)
            e=calc(l,r,v,2*x+2,mid,rx);
        return e;
    }
    int calc(int l,int r,int v)
    {
        return calc(l,r,v,0,0,siz-1);
    }
};
void preprocess() {}
void solve()
{
    int n,q;
    cin>>n>>q;
    segtree st;
    st.init(n);
    for(int i=0;i<n;i++)
        st.Set(i,1e9+2);
    while(q--)
    {
        char x;
        cin>>x;
        if(x=='M')
        {
            int a,b;
            cin>>a>>b;
            b--;
            st.Set(b,a);
        }
        else
        {
            int a,b;
            cin>>a>>b;
            b--;
            int haha=st.calc(b,n-1,a);
            if(haha==1e9+2)cout<<-1<<endl;
            else cout<<haha+1<<endl;
        }
    }
}
signed main()
{
    // freopen("div7.in","r",stdin);
    //freopen("div7.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    preprocess();
    //bla();
    int t=1;
   // cin>>t;
    while(t--)
        solve();
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	596 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	2 ms	348 KB	Output is correct
4	Correct	77 ms	9032 KB	Output is correct
5	Correct	75 ms	6504 KB	Output is correct
6	Correct	81 ms	8788 KB	Output is correct
7	Correct	87 ms	8788 KB	Output is correct