Submission #634231

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
634231	2022-08-24T07:26:53 Z	beedle	Deda (COCI17_deda)	C++17	140 / 140	952 ms	7636 KB

deda

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#include <iterator>
#include <stack>
#include <map>
#include <math.h>
#include <bitset>
#include <deque>
#include <string>
#include <tuple>
#include <queue>
#include <numeric>
#include <unordered_set>
#include <unordered_map>
#define pi 3.141592653589793238
#define ll long long
#define ld long double
#define rep(i, a, b) for (long long i = a; i <= b; i++)
#define mod 998244353ll
#define INF 1000000000000000000
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define all(x) (x).begin (), (x).end ()
#define sz(x) (ll) (x).size ()
#define reunique(v) v.resize(std::unique(v.begin(), v.end()) - v.begin())
#define rank rnk
#define log lg
#define fast                                                                  \
    ios_base::sync_with_stdio (false);                                        \
    cin.tie (NULL);                                                           \
    cout.tie (NULL)
 
using namespace std;

int t[4*2*100000+100];

void build(int a[], int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = a[tl];
    } else {
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        t[v] = min(t[v*2] , t[v*2+1]);
    }
}

int sum(int v, int tl, int tr, int l, int r) {
    if (l > r) 
        return mod;
    if (l == tl && r == tr) {
        return t[v];
    }
    int tm = (tl + tr) / 2;
    return min(sum(v*2, tl, tm, l, min(r, tm))
           , sum(v*2+1, tm+1, tr, max(l, tm+1), r));
}

void update(int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) {
        t[v] = new_val;
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v*2, tl, tm, pos, new_val);
        else
            update(v*2+1, tm+1, tr, pos, new_val);
        t[v] = min(t[v*2] , t[v*2+1]);
    }
}

signed main()
{
    fast;

    int n,q;
    cin>>n>>q;

    int arr[n+1];
    fill(arr,arr+n+1,mod);

    build(arr,1,1,n);

    while(q--)
    {
        char c;
        cin>>c;

        if(c=='M')
        {
            int loc,idx;
            cin>>loc>>idx;
            update(1,1,n,idx,loc);
        }
        else if(c=='D')
        {
            int maxval,idx;
            cin>>maxval>>idx;

            int lo=idx;
            int hi=n;
            int ans=-1;
            while(lo<=hi)
            {
                int mid=(lo+hi)/2;
                int q=sum(1,1,n,idx,mid);
                if(q<=maxval)
                {
                    hi=mid-1;
                    ans=mid;
                }
                else
                {
                    lo=mid+1;
                }
            }
            cout<<ans<<endl;
        }
    }

    return 0;
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	328 KB	Output is correct
3	Correct	8 ms	472 KB	Output is correct
4	Correct	952 ms	7524 KB	Output is correct
5	Correct	544 ms	5708 KB	Output is correct
6	Correct	651 ms	7340 KB	Output is correct
7	Correct	732 ms	7636 KB	Output is correct