oj.uz

Submission #860497

# Submission time Handle Problem Language Result Execution time Memory
860497 2023-10-13T06:56:16 Z VicBVic Deda (COCI17_deda) C++17
0 / 140
 76 ms 8528 KB 
#include <bits/stdc++.h>
using namespace std;

const int MN= 5e5+5;
const int MV= 19+5;
int arb[MN*4];
int v[MN];
int n,m;

int cmp(int a, int b)
{
    return v[a]<=v[b]?a:b;
}

void update(int nod, int st, int dr, int poz, int val)
{
    if(st==dr)
    {
        //cerr<<"here "<<nod<<','<<poz<<' '<<dr<<'\n';
        v[poz]=val;
        arb[nod]=poz;
        return;
    }
    
    int mid=(st+dr)/2;
    if(poz<=mid) update(nod*2, st, mid, poz, val);
    else update(nod*2+1, mid+1, dr, poz, val);
    
    arb[nod]=cmp(arb[nod*2], arb[nod*2+1]);
}

int query(int nod, int st, int dr, int qst, int val)
{
    if(dr<qst) return 0;
    
    if(qst<=st && v[arb[nod]]<=val)
    {
        return arb[nod];
    }
    
    if(qst<=st && v[arb[nod]]>val)
    {
        return 0;
    }
    
    int mid=(st+dr)/2;
    return cmp(query(nod*2, st, mid, qst, val),
                query(nod*2+1, mid+1, dr, qst, val));
}

void printArb()
{
    int p=1;
    for(int i=1;i<=4*n;i++)
    {
        cerr<<arb[i]<<' ';
        if(p==i)
        {
            cerr<<'\n';
            p=p<<1^1;
        }
    }
}

int main()
{
    ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    v[0]=MV;
    
    
    
    cin>>n>>m;
    
    char c; int b,y;
    for(int i=1;i<=m;i++)
    {
        cin>>c>>y>>b;
        if(c=='M')
        {
            //cerr<<"poz "<<b<<" val "<<y<<'\n';
            update(1,1,n,b,y);
        }
        else
        {
            int ans=query(1,1,n,b,y);
            cout<<(ans==0?-1:ans)<<'\n';
        }
        //printArb();
    }

    return 0;
}

Subtask #1
0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Incorrect 2 ms 2396 KB Output isn't correct
4 Incorrect 75 ms 8528 KB Output isn't correct
5 Incorrect 71 ms 8304 KB Output isn't correct
6 Incorrect 76 ms 8388 KB Output isn't correct
7 Incorrect 74 ms 8464 KB Output isn't correct