oj.uz

Submission #341277

# Submission time Handle Problem Language Result Execution time Memory
341277 2020-12-29T10:44:19 Z Dilshod_Imomov Simple game (IZhO17_game) C++17
100 / 100
 277 ms 19948 KB 
# include <bits/stdc++.h>
# define speed ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
# define int long long
# define fi first
# define se second
 
using namespace std;
 
const int N = 1e6 + 7;
const int mod = 1e9 + 7;

int a[N], t[4 * N];

void upd( int v, int l, int r, int pos, int add ) {
    if ( l == r ) {
        t[v] += add;
        return;
    }
    int m = (l + r) / 2;
    if ( pos <= m ) {
        upd( v * 2, l, m, pos, add );
    }
    else {
        upd( v * 2 + 1, m + 1, r, pos, add );
    }
    t[v] = t[v * 2] + t[v * 2 + 1];
}

int get( int v, int tl, int tr, int l, int r ) {
    if ( l > r ) {
        return 0;
    }
    if ( tl == l && tr == r ) {
        return t[v];
    }
    int m = (tl + tr) / 2;
    int sm = get( v * 2, tl, m, l, min( r, m ) );
    sm += get( v * 2 + 1, m + 1, tr, max( l, m + 1 ), r );
    return sm;
}

int32_t main() {
    speed; 
    int n, m;
    cin >> n >> m;
    for ( int i = 1; i <= n; i++ ) {
        cin >> a[i];
    }
    int MAXN = 1e6;
    for ( int i = 2; i <= n; i++ ) {
        int l = a[i - 1], r = a[i];
        if ( l > r ) {
            swap( l, r );
        }
        // dp[l]++;
        upd( 1, 1, MAXN, l, 1 );
        upd( 1, 1, MAXN, r + 1, -1 );
        // dp[r + 1]--;
    }
    for ( int i = 1; i <= m; i++ ) {
        int t;
        cin >> t;
        if ( t == 2 ) {
            int h, cnt = 0;
            cin >> h;
            cout << get( 1, 1, MAXN, 1, h ) << '\n';
        }
        else {
            int pos, val;
            cin >> pos >> val;
            if ( pos != 1 ) {
                int l = a[pos - 1], r = a[pos];
                if ( l > r ) {
                    swap( l, r );
                }
                upd( 1, 1, MAXN, l, -1 );
                upd( 1, 1, MAXN, r + 1, 1 );
            }
            if ( pos != n ) {
                int l = a[pos], r = a[pos + 1];
                if ( l > r ) {
                    swap( l, r );
                }
                upd( 1, 1, MAXN, l, -1 );
                upd( 1, 1, MAXN, r + 1, 1 );
            }
            a[pos] = val;
            if ( pos != 1 ) {
                int l = a[pos - 1], r = a[pos];
                if ( l > r ) {
                    swap( l, r );
                }
                upd( 1, 1, MAXN, l, 1 );
                upd( 1, 1, MAXN, r + 1, -1 );
            }
            if ( pos != n ) {
                int l = a[pos], r = a[pos + 1];
                if ( l > r ) {
                    swap( l, r );
                }
                upd( 1, 1, MAXN, l, 1 );
                upd( 1, 1, MAXN, r + 1, -1 );
            }
        }
    }
}

Compilation message

game.cpp: In function 'int32_t main()':
game.cpp:64:20: warning: unused variable 'cnt' [-Wunused-variable]
   64 |             int h, cnt = 0;
      |                    ^~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 9 ms 11884 KB Output is correct
3 Correct 8 ms 11500 KB Output is correct
4 Correct 8 ms 11628 KB Output is correct
5 Correct 11 ms 11628 KB Output is correct
6 Correct 11 ms 11904 KB Output is correct
7 Correct 2 ms 492 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 9 ms 11884 KB Output is correct
3 Correct 8 ms 11500 KB Output is correct
4 Correct 8 ms 11628 KB Output is correct
5 Correct 11 ms 11628 KB Output is correct
6 Correct 11 ms 11904 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 72 ms 1388 KB Output is correct
9 Correct 139 ms 18156 KB Output is correct
10 Correct 157 ms 18176 KB Output is correct
11 Correct 73 ms 1388 KB Output is correct
12 Correct 96 ms 2284 KB Output is correct
13 Correct 86 ms 1772 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 9 ms 11884 KB Output is correct
3 Correct 8 ms 11500 KB Output is correct
4 Correct 8 ms 11628 KB Output is correct
5 Correct 11 ms 11628 KB Output is correct
6 Correct 11 ms 11904 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 72 ms 1388 KB Output is correct
9 Correct 139 ms 18156 KB Output is correct
10 Correct 157 ms 18176 KB Output is correct
11 Correct 73 ms 1388 KB Output is correct
12 Correct 96 ms 2284 KB Output is correct
13 Correct 86 ms 1772 KB Output is correct
14 Correct 277 ms 17900 KB Output is correct
15 Correct 254 ms 19820 KB Output is correct
16 Correct 249 ms 19820 KB Output is correct
17 Correct 250 ms 19820 KB Output is correct
18 Correct 251 ms 19948 KB Output is correct