제출 #1186696

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1186696		prideliqueee	Deda (COCI17_deda)	C++20	140 / 140	72 ms	11076 KiB

deda

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
int s[200010];
pair<int,int> mn[800000];
int ans;
void update(int l,int r,int i,int index,int val)
{
    if(index<l||index>r)
    return;
    if(l==r)
    {
        mn[i]={val,val};
        return;
    }
    int mid=(l+r)/2;
    update(l,mid,i*2,index,val);
    update(mid+1,r,i*2+1,index,val);
    mn[i]={mn[i*2].f,min(mn[i*2].s,mn[i*2+1].s)};
}
void query(int l,int r,int i,int index,int val)
{
    if(index>r)
    return;
    if(l>=index&&mn[i].f<=val)
    {
        ans=min(ans,l);
        return;
    }
    if(mn[i].s>val)
    return;
    int mid=(l+r)/2;
    query(l,mid,i*2,index,val);
    if(ans<800000)
    return;
    else
    query(mid+1,r,i*2+1,index,val);
}
void build(int l,int r,int i)
{
    if(l==r)
    {
        mn[i]={LLONG_MAX,LLONG_MAX};
        return;
    }
    int mid=(l+r)/2;
    build(l,mid,i*2);
    build(mid+1,r,i*2+1);
    mn[i]={mn[i*2].f,min(mn[i*2].s,mn[i*2+1].s)};
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,q;
    cin>>n>>q;
    build(1,n,1);
    while(q--)
    {
        char c;
        cin>>c;
        if(c=='M')
        {
            int x,a;
            cin>>x>>a;
            if(s[a]<x)
            {
                s[a]=x;
                update(1,n,1,a,x);
            }
        }
        else
        {
            int y,b;
            cin>>y>>b;
            ans=LLONG_MAX;
            if(mn[1].s>y)
            {
                cout<<-1<<'\n';
                continue;
            }
            query(1,n,1,b,y);
            if(ans<LLONG_MAX)
            cout<<ans<<'\n';
            else
            cout<<-1<<'\n';
        }
    }
}

• Subtask 1: 140 / 140