Submission #619581

#	Time	Username	Problem	Language	Result	Execution time	Memory
619581		nohaxjustsoflo	Simple game (IZhO17_game)	C++17	100 / 100	439 ms	15484 KiB

game

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> order_set;
mt19937 mt_rand(chrono::high_resolution_clock::now().time_since_epoch().count());
//uniform_int_distribution<int> gen; ///(min, max)
//int random() {return gen(mt_rand);}
const int mxN=3e5+5;
const int mod=998244353;
const int mxlogN=20;
const int mxK=26;
const int inf=2e9;
const int K=600;
int a[mxN];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m; cin >> n >> m;
    order_set add,sub;
    for(int i=0; i<n; i++)
    {
        cin >> a[i];
        if(i) add.insert(min(a[i],a[i-1]));
        if(i) sub.insert(max(a[i],a[i-1]));
    }
    for(int i=0; i<m; i++)
    {
        int t; cin >> t;
        if(t==1)
        {
            int i,v; cin >> i >> v; i--;
            if(i > 0) add.erase(add.lower_bound(min(a[i],a[i-1])-1));
            if(i > 0) sub.erase(sub.lower_bound(max(a[i],a[i-1])-1));
            if(i+1<n) add.erase(add.lower_bound(min(a[i],a[i+1])-1));
            if(i+1<n) sub.erase(sub.lower_bound(max(a[i],a[i+1])-1));
            a[i]=v;
            if(i > 0) add.insert(min(a[i],a[i-1]));
            if(i > 0) sub.insert(max(a[i],a[i-1]));
            if(i+1<n) add.insert(min(a[i],a[i+1]));
            if(i+1<n) sub.insert(max(a[i],a[i+1]));
        }
        else
        {
            int H; cin >> H;
            cout << add.order_of_key(H)-sub.order_of_key(H) << "\n";
        }
    }
}

• Subtask 1: 22 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51