oj.uz

답안 #466691

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
466691 2021-08-20T08:12:03 Z ak2006 Deda (COCI17_deda) C++14
60 / 140
 1000 ms 19592 KB 
#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 = max(root->lc->m,root->rc->m);
}
ll walk(Node*root,int b,int y)
{
    if (root->r < b)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
60.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 4 ms 460 KB Output is correct
4 Execution timed out 1088 ms 19120 KB Time limit exceeded
5 Execution timed out 1050 ms 10928 KB Time limit exceeded
6 Execution timed out 1096 ms 15044 KB Time limit exceeded
7 Execution timed out 1083 ms 19592 KB Time limit exceeded