oj.uz

Submission #167082

# Submission time Handle Problem Language Result Execution time Memory
167082 2019-12-05T13:44:20 Z hentai_lover Simple game (IZhO17_game) C++14
0 / 100
 6 ms 4344 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 = 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){
        ll x = a[i];
        ll y = a[i - 1];
        if(x > y)swap(x, y);
        t.add(x, 1);
        t.add(y, -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) << "\n";
        }
    }
}


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

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4216 KB Output is correct
2 Correct 6 ms 4344 KB Output is correct
3 Incorrect 6 ms 4344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4216 KB Output is correct
2 Correct 6 ms 4344 KB Output is correct
3 Incorrect 6 ms 4344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4216 KB Output is correct
2 Correct 6 ms 4344 KB Output is correct
3 Incorrect 6 ms 4344 KB Output isn't correct
4 Halted 0 ms 0 KB -