답안 #860506

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
860506	2023-10-13T07:12:24 Z	VicBVic	Deda (COCI17_deda)	C++17	0 / 140	79 ms	4624 KB

deda

#include <bits/stdc++.h>
using namespace std;

const int MN= 2e5+5;
const int MV= 1e9+5;
int arb[MN*4];
int n,m;

void update(int nod, int st, int dr, int poz, int val)
{
    if(st==dr)
    {
        //cerr<<"here "<<nod<<','<<poz<<' '<<dr<<'\n';
        arb[nod]=val;
        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]=min(arb[nod*2], arb[nod*2+1]);
}

int query(int nod, int st, int dr, int qst, int val)
{
    if(dr<qst) return dr+1;
    
    if(qst<=st && arb[nod]<=val)
    {
        return st;
    }
    
    if(qst<=st && arb[nod]>val)
    {
        return dr+1;
    }
    
    int mid=(st+dr)/2;
    int st_cb=query(nod*2, st, mid, qst, val);
    if(st_cb!=mid+1)
    {
        return st_cb;
    }
    return 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);
    
    memset(arb, 0x3f, sizeof(arb));
    
    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==n+1?-1:ans)<<'\n';
        }
        //printArb();
    }

    return 0;
}
/*
10 10
M 20 10
D 1 9
M 2 3
D 17 10
M 20 2
D 8 2
M 40 1
D 25 2
M 33 9
D 37 9

3 4
M 10 3
M 5 1
D 20 2
D 5 1
*/

Subtask #1

0 / 140.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	3416 KB	Output isn't correct
2	Incorrect	1 ms	3420 KB	Output isn't correct
3	Incorrect	2 ms	3420 KB	Output isn't correct
4	Incorrect	68 ms	4624 KB	Output isn't correct
5	Incorrect	65 ms	4196 KB	Output isn't correct
6	Incorrect	72 ms	4436 KB	Output isn't correct
7	Incorrect	79 ms	4432 KB	Output isn't correct