oj.uz

Submission #167187

# Submission time Handle Problem Language Result Execution time Memory
167187 2019-12-06T09:47:09 Z hentai_lover Simple game (IZhO17_game) C++14
100 / 100
 109 ms 14748 KB 
#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 = 2e6;

ll n, Q, x, y;
ll a[N], kol[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, 2, n){
        ll x = a[i];
        ll y = a[i - 1];
        if(x > y)swap(x, y);
        kol[x] ++;
        if(x != y)kol[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;
            if(x != 1){
                f = a[x], s = a[x - 1];
                if(f > s)swap(f, s);
                if(f != s)kol[s] --, kol[f] --;
                t.add(f, -1);
                t.add(s + 1, 1);
            }
            if(x != n){
                f = a[x], s = a[x + 1];
                if(f > s)swap(f, s);
                if(f != s)kol[s] --, kol[f] --;
                t.add(f, -1);
                t.add(s + 1, 1);
            }

            a[x] = y;
            if(x != 1){
                f = a[x], s = a[x - 1];
                if(f > s)swap(f, s);
                if(f != s)kol[s] ++, kol[f] ++;
                t.add(f, 1);
                t.add(s + 1, -1);
            }
            if(x != n){
                f = a[x], s = a[x + 1];
                if(f > s)swap(f, s);
                if(f != s)kol[s] ++, kol[f] ++;
                t.add(f, 1);
                t.add(s + 1, -1);
            }

        }   else{
            cin >> x;
            ll ans = t.get(x) - kol[x] / 2 + (a[1] == x);
            //cout << "     " << t.get(x) << endl;
            cout << ans << "\n";
        }
    }
}


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

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8184 KB Output is correct
2 Correct 12 ms 11256 KB Output is correct
3 Correct 13 ms 11128 KB Output is correct
4 Correct 13 ms 11260 KB Output is correct
5 Correct 11 ms 11256 KB Output is correct
6 Correct 13 ms 11384 KB Output is correct
7 Correct 11 ms 8244 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8184 KB Output is correct
2 Correct 12 ms 11256 KB Output is correct
3 Correct 13 ms 11128 KB Output is correct
4 Correct 13 ms 11260 KB Output is correct
5 Correct 11 ms 11256 KB Output is correct
6 Correct 13 ms 11384 KB Output is correct
7 Correct 11 ms 8244 KB Output is correct
8 Correct 58 ms 9592 KB Output is correct
9 Correct 81 ms 14684 KB Output is correct
10 Correct 83 ms 14748 KB Output is correct
11 Correct 58 ms 9464 KB Output is correct
12 Correct 60 ms 10744 KB Output is correct
13 Correct 72 ms 10680 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8184 KB Output is correct
2 Correct 12 ms 11256 KB Output is correct
3 Correct 13 ms 11128 KB Output is correct
4 Correct 13 ms 11260 KB Output is correct
5 Correct 11 ms 11256 KB Output is correct
6 Correct 13 ms 11384 KB Output is correct
7 Correct 11 ms 8244 KB Output is correct
8 Correct 58 ms 9592 KB Output is correct
9 Correct 81 ms 14684 KB Output is correct
10 Correct 83 ms 14748 KB Output is correct
11 Correct 58 ms 9464 KB Output is correct
12 Correct 60 ms 10744 KB Output is correct
13 Correct 72 ms 10680 KB Output is correct
14 Correct 106 ms 14720 KB Output is correct
15 Correct 109 ms 14736 KB Output is correct
16 Correct 109 ms 14692 KB Output is correct
17 Correct 103 ms 14712 KB Output is correct
18 Correct 105 ms 14712 KB Output is correct