oj.uz

Submission #168166

# Submission time Handle Problem Language Result Execution time Memory
168166 2019-12-11T17:43:02 Z muhammad_hokimiyon Simple game (IZhO17_game) C++14
100 / 100
 79 ms 7772 KB 
#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")

#define fi first
#define se second
#define ll long long

using namespace std;

const int N = 1e6 + 7;
const int mod = 1e9 + 7;

int n,q;
int a[N];
int t[N];
int l[N];
int r[N];

void upd( int x , int g )
{
    while( x < N ){
        t[x] += g;
        x += x & -x;
    }
}

int get( int x )
{
    int res = 0;
    while( x > 0 ){
        res += t[x];
        x -= x & -x;
    }
    return res;
}

void solve()
{
    cin >> n >> q;
    for( int i = 1; i <= n; i++ ){
        cin >> a[i];
    }
    for( int i = 1; i < n; i++ ){
        l[i] = min(a[i] , a[i + 1]);
        r[i] = max(a[i] , a[i + 1]) + 1;
        upd(l[i] , 1);
        upd(r[i] , -1);
    }
    for( int i = 1; i <= q; i++ ){
        int tp;
        cin >> tp;
        if( tp == 1 ){
            int x , y;
            cin >> x >> y;
            if( x < n ){
                upd(l[x] , -1);
                upd(r[x] , 1);
            }
            if( x > 1 ){
                upd(l[x - 1] , -1);
                upd(r[x - 1], 1);
            }
            a[x] = y;
            if( x < n ){
                l[x] = min(a[x] , a[x + 1]);
                r[x] = max(a[x] , a[x + 1]) + 1;
                upd(l[x] , 1);
                upd(r[x] , -1);
            }
            if( x > 1 ){
                l[x - 1] = min(a[x] , a[x - 1]);
                r[x - 1] = max(a[x] , a[x - 1]) + 1;
                upd(l[x - 1] , 1);
                upd(r[x - 1] , -1);
            }
        }
        else{
            int h;
            cin >> h;
            cout << get(h) << "\n";
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen( "input.txt" , "r" , stdin );
    //freopen( "output.txt" , "w" , stdout );

    int t = 1;//cin >> t;
    while( t-- ){
        solve();
    }
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 5 ms 3832 KB Output is correct
3 Correct 5 ms 3960 KB Output is correct
4 Correct 5 ms 3960 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 5 ms 3960 KB Output is correct
7 Correct 3 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 5 ms 3832 KB Output is correct
3 Correct 5 ms 3960 KB Output is correct
4 Correct 5 ms 3960 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 5 ms 3960 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 46 ms 2624 KB Output is correct
9 Correct 57 ms 7772 KB Output is correct
10 Correct 59 ms 7708 KB Output is correct
11 Correct 47 ms 2552 KB Output is correct
12 Correct 50 ms 3704 KB Output is correct
13 Correct 53 ms 3704 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 5 ms 3832 KB Output is correct
3 Correct 5 ms 3960 KB Output is correct
4 Correct 5 ms 3960 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 5 ms 3960 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 46 ms 2624 KB Output is correct
9 Correct 57 ms 7772 KB Output is correct
10 Correct 59 ms 7708 KB Output is correct
11 Correct 47 ms 2552 KB Output is correct
12 Correct 50 ms 3704 KB Output is correct
13 Correct 53 ms 3704 KB Output is correct
14 Correct 75 ms 7772 KB Output is correct
15 Correct 75 ms 7644 KB Output is correct
16 Correct 79 ms 7672 KB Output is correct
17 Correct 76 ms 7676 KB Output is correct
18 Correct 76 ms 7672 KB Output is correct