oj.uz

Submission #929145

# Submission time Handle Problem Language Result Execution time Memory
929145 2024-02-17T18:37:46 Z sondos225 Deda (COCI17_deda) C++17
60 / 140
 1000 ms 32348 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define yes "YES"
#define no "NO"
#define bigg INT_MAX
#define debug(x) cout<<(#x)<<" = " <<x<<endl;
#define all(x) x.begin(),x.end()
#define sz size()
#define nn '\n'
#define mms(x,y) memset(x,y,sizeof(x))
#define forr(i,j,n) for (int i=j; i<n; i++)
#define forn(i,j,n) for (int i=j; i>n; i--)
#define fi first
#define se second
#define la "LA"
#define cinn(x,y) for(int i=0; i<y; i++) cin>>x[i];
#define pii pair<int,int>
#define tii tuple<int,int,int>
pii seg[1000000];
void edit(int ll, int rr, int i, int idx, int val)
{
    if (ll==rr && ll==idx)
    {
        if (val<seg[i].fi)
        {
            seg[i]={val,idx};
        }
        else if (val==seg[i].fi) seg[i].se=min(idx,seg[i].se);
        return;
    }
    int m=(ll+rr)/2;
    if (idx<=m)
    {
        edit(ll,m,(2*i)+1,idx, val);
    }
    else edit(m+1,rr,(2*i)+2,idx,val);
    seg[i]=min(seg[(2*i)+1],seg[(2*i)+2]);
    return;
}
int query(int ll, int rr, int i, int l, int val)
{int m=(ll+rr)/2;
    int mn=seg[i].fi;
    int idx=seg[i].se;
    if (mn<=val && idx>=l) return min(idx,min(query(m+1,rr,(i*2)+2,l,val),query(ll,m,(i*2)+1,l,val)));
    if (mn>val) return bigg;
    if (l>m) return query(m+1,rr,(i*2)+2,l,val);
    return min(query(m+1,rr,(i*2)+2,l,val),query(ll,m,(i*2)+1,l,val));
}
signed main()
{
//    #ifndef LOCAL
//    freopen("helpcross.in","r",stdin);
//    freopen("helpcross.out","w", stdout);
//    #endif
    fast
    forr(i,0,1000000) seg[i]={bigg,0};
    int n,q;
    cin>>n >>q;
    while(q--)
    {
        char w;
        int x,y;
        cin>>w >>x >>y;
        if (w=='M')
        {
            edit(1,n,0,y,x);
        }
        else
        {
            int ans=query(1,n,0,y,x);
            if (ans==bigg) ans=-1;
            cout<<ans<<nn;
        }
    }
    return 0;
}

Subtask #1
60.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15964 KB Output is correct
2 Correct 3 ms 15964 KB Output is correct
3 Correct 9 ms 15964 KB Output is correct
4 Runtime error 25 ms 32348 KB Execution killed with signal 11
5 Execution timed out 1038 ms 16216 KB Time limit exceeded
6 Runtime error 15 ms 32344 KB Execution killed with signal 11
7 Runtime error 17 ms 32092 KB Execution killed with signal 11