Submission #466692

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
466692	2021-08-20T08:16:17 Z	ak2006	Deda (COCI17_deda)	C++14	140 / 140	185 ms	23492 KB

deda

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
void setIO()
{
    fast;
}
struct Node
{
    int l,r;
    ll m = inf;
    Node*lc = NULL;
    Node*rc = NULL;
    Node(int L,int R)
    {
        l = L,r = R;
        if (l != r){
            int mid = (l + r)/2;
            lc = new Node(l,mid);
            rc = new Node(mid + 1,r);
        }
    }
};
void update(Node*root,int i,int v)
{
    if (!(root->l <= i and i <= root->r))return;
    if (root->l == root->r){
        root->m = v;
        return;
    }
    update(root->lc,i,v);
    update(root->rc,i,v);
    root->m = min(root->lc->m,root->rc->m);
}
ll walk(Node*root,int b,ll y)
{
    if (root->r < b)return inf;
    if (root->m > y)return inf;
    if (root->l == root->r)
        return (root->m <= y ? root->l : inf);
    ll v1 = walk(root->lc,b,y);
    if (v1 == inf)return walk(root->rc,b,y);
    return v1;
}
int main()
{
    setIO();
    int n,q;
    cin>>n>>q;
    Node*root = new Node(1,n);
    while (q--){
        char t;
        int x,a;
        cin>>t>>x>>a;
        if (t == 'M')update(root,a,x);
        else {
            ll ans = walk(root,a,x);
            if (ans == inf)cout<<-1<<'\n';
            else cout<<ans<<'\n';
        }
    }
    return 0;
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	2 ms	332 KB	Output is correct
4	Correct	116 ms	23492 KB	Output is correct
5	Correct	146 ms	12664 KB	Output is correct
6	Correct	162 ms	18184 KB	Output is correct
7	Correct	185 ms	23048 KB	Output is correct