oj.uz

Submission #170197

# Submission time Handle Problem Language Result Execution time Memory
170197 2019-12-24T08:20:07 Z andrew Simple game (IZhO17_game) C++17
100 / 100
 96 ms 11384 KB 
#include <bits/stdc++.h>

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

#define fi first
#define se second
#define p_b push_back
#define pll pair<ll,ll>
#define pii pair<int,int>
#define m_p make_pair
#define all(x) x.begin(),x.end()
#define sset ordered_set
#define sqr(x) (x)*(x)
#define pw(x) (1ll << x)
#define sz(x) (int)x.size()

using namespace std;
typedef long long ll;
typedef long double ld;
const ll MAXN = 1123456;
const ll N = 1e6;
const ll inf = 3e18;
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());

template <typename T> void vout(T s){cout << s << endl;exit(0);}

ll t[N + 2];

void u(ll pos, ll val){
    for(; pos <= N; pos += pos & -pos)t[pos] += val;
}

ll f(ll pos){
    ll res = 0;
    for(; pos > 0; pos -= pos & -pos)res += t[pos];
    return res;
}

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

    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif // LOCAL


    ll n, m;
    cin >> n >> m;
    vector <ll> a(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }

    for(int i = 2; i <= n; i++){
        if(a[i - 1] <= a[i]){
            ll l = a[i - 1], r = a[i] - 1;
            if(i == n)r++;
            u(l, 1);
            u(r + 1, -1);
        }else{
            ll l = a[i] + 1, r = a[i - 1];
            if(i == n)l++;
            u(l, 1);
            u(r + 1, -1);
        }
    }

    while(m--){
        ll t;
        cin >> t;
        if(t == 2){
            ll h;
            cin >> h;
            cout << f(h) << "\n";
        }else{
            ll pos, val;
            cin >> pos >> val;
            ll l, r;
            if(pos > 1){
                if(a[pos - 1] <= a[pos]){
                    l = a[pos - 1], r = a[pos] - 1;
                    if(pos == n)r++;
                    u(l, -1);
                    u(r + 1, 1);
                }else{
                    l = a[pos] + 1, r = a[pos - 1];
                    if(pos == n)l++;
                    u(l, -1);
                    u(r + 1, 1);
                }
            }
            if(pos < n){
                if(a[pos] <= a[pos + 1]){
                    l = a[pos], r = a[pos + 1] - 1;
                    if(pos + 1 == n)r++;
                    u(l, -1);
                    u(r + 1, 1);
                }else{
                    l = a[pos + 1] + 1, r = a[pos];
                    if(pos + 1 == n)l++;
                    u(l, -1);
                    u(r + 1, 1);
                }
            }
            a[pos] = val;
            if(pos > 1){
                if(a[pos - 1] <= a[pos]){
                    l = a[pos - 1], r = a[pos] - 1;
                    if(pos == n)r++;
                    u(l, 1);
                    u(r + 1, -1);
                }else{
                    l = a[pos] + 1, r = a[pos - 1];
                    if(pos == n)l++;
                    u(l, 1);
                    u(r + 1, -1);
                }
            }
            if(pos < n){
                if(a[pos] <= a[pos + 1]){
                    l = a[pos], r = a[pos + 1] - 1;
                    if(pos + 1 == n)r++;
                    u(l, 1);
                    u(r + 1, -1);
                }else{
                    l = a[pos + 1] + 1, r = a[pos];
                    if(pos + 1 == n)l++;
                    u(l, 1);
                    u(r + 1, -1);
                }
            }
        }
    }


    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 8 ms 6264 KB Output is correct
3 Correct 7 ms 6136 KB Output is correct
4 Correct 8 ms 6264 KB Output is correct
5 Correct 9 ms 6136 KB Output is correct
6 Correct 9 ms 6392 KB Output is correct
7 Correct 5 ms 376 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 8 ms 6264 KB Output is correct
3 Correct 7 ms 6136 KB Output is correct
4 Correct 8 ms 6264 KB Output is correct
5 Correct 9 ms 6136 KB Output is correct
6 Correct 9 ms 6392 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 47 ms 2200 KB Output is correct
9 Correct 70 ms 11228 KB Output is correct
10 Correct 67 ms 11128 KB Output is correct
11 Correct 47 ms 2152 KB Output is correct
12 Correct 52 ms 3448 KB Output is correct
13 Correct 54 ms 3264 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 8 ms 6264 KB Output is correct
3 Correct 7 ms 6136 KB Output is correct
4 Correct 8 ms 6264 KB Output is correct
5 Correct 9 ms 6136 KB Output is correct
6 Correct 9 ms 6392 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 47 ms 2200 KB Output is correct
9 Correct 70 ms 11228 KB Output is correct
10 Correct 67 ms 11128 KB Output is correct
11 Correct 47 ms 2152 KB Output is correct
12 Correct 52 ms 3448 KB Output is correct
13 Correct 54 ms 3264 KB Output is correct
14 Correct 94 ms 11236 KB Output is correct
15 Correct 93 ms 11256 KB Output is correct
16 Correct 94 ms 11312 KB Output is correct
17 Correct 92 ms 11384 KB Output is correct
18 Correct 96 ms 11260 KB Output is correct