Submission #1303498

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303498		yusifm	Deda (COCI17_deda)	C++20	140 / 140	583 ms	7612 KiB

deda

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define str string
#define pb push_back
#define pf push_front
#define in insert
#define all(v) v.begin(),v.end()
#define fastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int sz=1000000,INF=1000000000;
using namespace std;
vector<ll>mins;
ll getMin(ll left,ll right,ll index,ll Left,ll Right)
{
    if(left>Right || right<Left)
    {
        return INF;
    }
    if(left>=Left && right<=Right)
    {
        return mins[index];
    }
    else
    {
        ll middle=(left+right)/2;
        return min(getMin(left,middle,2*index,Left,Right),getMin(middle+1,right,2*index+1,Left,Right));
    }
}
void update(ll left,ll right,ll index,ll Index,ll Num)
{
    if(Index>=left && Index<=right)
    {
        if(left==right)
        {
            mins[index]=Num;
        }
        else
        {
            ll middle=(left+right)/2;
            if(Index<=middle)
            {
                update(left,middle,2*index,Index,Num);
            }
            else
            {
                update(middle+1,right,2*index+1,Index,Num);
            }
            mins[index]=min(mins[2*index],mins[2*index+1]);
        }
    }
}
void solve()
{
    ll n,m,num1,num2,left,right,middle,ans;
    char c;
    cin>>n>>m;
    mins.resize(4*n+1),fill(all(mins),INF);
    for(int i=0;i<m;i++)
    {
        cin>>c>>num1>>num2;
        if(c=='D')
        {
            left=num2,right=n,ans=-1;
            while(left<=right)
            {
                middle=(left+right)/2;
                if(getMin(1,n,1,num2,middle)>num1)
                {
                    left=middle+1;
                }
                else
                {
                    right=middle-1,ans=middle;
                }
            }
            cout<<ans<<"\n";
        }
        else
        {
            update(1,n,1,num2,num1);
        }
    }
}
int main()
{
    fastIO;
    ll t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
}

• Subtask 1: 140 / 140