Submission #167089

#	Time	Username	Problem	Language	Result	Execution time	Memory
167089		hentai_lover	Simple game (IZhO17_game)	C++14	22 / 100	51 ms	5112 KiB

game

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#define pb push_back
#define fr(i, l, r) for(ll i = l; i <= r; ++ i)
#define rf(i, r, l) for(ll i = l; i >= r; -- i)

using namespace std;
using namespace __gnu_pbds;

template <typename T>
using _set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef int ll;
typedef pair<ll, ll> pll;

const ll oo = ll(1e9) + 10;

const ll N = 1e6 + 10;

ll n, Q, x, y;
ll a[N];

struct FenvikTree{
    vector <ll> t;
    void uni(){
        t.resize(N + 10);
    }

    void add(ll x, ll y){
        for(ll i = x; i <= N; i += i & -i)t[i] += y;
    }
    ll get(ll x){
        ll ans = 0;
        for(ll i = x; i >= 1; i -= i & -i)ans += t[i];
        return ans;
    }
} t;

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    t.uni();
    cin >> n >> Q;
    fr(i, 1, n)cin >> a[i];
    a[0] = a[1];
    a[n + 1] = a[n];

    fr(i, 1, n + 1){
        ll x = a[i];
        ll y = a[i - 1];
        if(x > y)swap(x, y);
        t.add(x, 1);
        t.add(y + 1, -1);
    }

    fr(z, 1, Q){
        ll k;
        cin >> k;
        if(k == 1){
            cin >> x >> y;
            //удалить
            ll f, s;
            f = a[x], s = a[x - 1];
            if(f > s)swap(f, s);
            t.add(f, -1);
            t.add(s + 1, 1);
            f = a[x], s = a[x + 1];
            if(f > s)swap(f, s);
            t.add(f, -1);
            t.add(s + 1, 1);

            a[x] = y;
            a[0] = a[1];
            a[n + 1] = a[n];

            f = a[x], s = a[x - 1];
            if(f > s)swap(f, s);
            t.add(f, 1);
            t.add(s + 1, -1);
            f = a[x], s = a[x + 1];
            if(f > s)swap(f, s);
            t.add(f, 1);
            t.add(s + 1, -1);

        }   else{
            cin >> x;
            cout << t.get(x + 1) << "\n";
        }
    }
}


/*
3 3
1 2 1
2 1
1 2 1
2 1
*/

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