oj.uz

Submission #1117373

# Submission time Handle Problem Language Result Execution time Memory
1117373 2024-11-23T12:53:37 Z danglayloi1 Deda (COCI17_deda) C++17
140 / 140
 75 ms 8008 KB 
#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=2e5+5;
int n, q, nod[nx<<2];
void update(int id, int l, int r, int p, int val)
{
    if(l>p || r<p)
        return;
    if(l==r)
        return void(nod[id]=val);
    int mid=(l+r)>>1;
    update(id<<1, l, mid, p, val);
    update(id<<1|1, mid+1, r, p, val);
    nod[id]=min(nod[id<<1], nod[id<<1|1]);
}
int find(int id, int l, int r, int lim, int val)
{
    if(nod[id]>val)
        return -1;
    if(r<lim)
        return -1;
    if(l==r)
        return l;
    int mid=(l+r)>>1;
    int res=-1;
    if(nod[id<<1]<=val)
        res=find(id<<1, l, mid, lim, val);
    if(res==-1)
        res=find(id<<1|1, mid+1, r, lim, val);
    return res;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>q;
    memset(nod, 0x3f, sizeof(nod));
    while(q--)
    {
        char c;
        int x, y;
        cin>>c>>x>>y;
        if(c=='M')
            update(1, 1, n, y, x);
        else cout<<find(1, 1, n, y, x)<<'\n';
    }
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3408 KB Output is correct
2 Correct 3 ms 3408 KB Output is correct
3 Correct 6 ms 3664 KB Output is correct
4 Correct 66 ms 8008 KB Output is correct
5 Correct 69 ms 7512 KB Output is correct
6 Correct 75 ms 7752 KB Output is correct
7 Correct 73 ms 8008 KB Output is correct