oj.uz

Submission #107723

# Submission time Handle Problem Language Result Execution time Memory
107723 2019-04-25T14:40:46 Z Shafin666 Simple game (IZhO17_game) C++14
100 / 100
 324 ms 7040 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define  read_input         freopen("in.txt","r", stdin)
#define  print_output       freopen("out.txt","w", stdout)
typedef long long ll;
typedef long double ld;
using namespace std;

const int maxn = 1e6+5;

struct BinaryIndexedTree {
    int a[maxn];

    void add(int idx, int v) {
        while(idx <= maxn) {
            a[idx] += v;
            idx += idx & -idx;
        }
    }

    int get(int idx) {
        int ret = 0;
        while(idx > 0) {
            ret += a[idx];
            idx -= idx & -idx;
        } return ret;
    }

    void update(int l, int r, int v) {
        if(l > r) swap(l, r);

        add(l, v);
        add(r+1, -v);
    }

    int query(int l, int r) {
        int ret = get(r);
        ret -= get(l-1);
        return ret;
    }
} BIT;

int main()
{   
    int n, m;
    int a[maxn];

    cin >> n >> m;
    for(int i = 1;  i <= n; i++) {
        cin >> a[i];
        if(i > 1) BIT.update(a[i], a[i-1], 1);
    }

    while(m--) {
        int ch;
        cin >> ch;

        if(ch == 1) {
            int pos, val;
            cin >> pos >> val;

            if(pos > 1) BIT.update(a[pos-1], a[pos], -1);
            if(pos < n) BIT.update(a[pos], a[pos+1], -1);

            a[pos] = val;

            if(pos > 1) BIT.update(a[pos-1], a[pos], 1);
            if(pos < n) BIT.update(a[pos], a[pos+1], 1);
        }
        
        else {
            int H;
            cin >> H;
            cout << BIT.get(H) << endl;
        }
    }
    return 0;   
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 9 ms 3968 KB Output is correct
3 Correct 8 ms 3968 KB Output is correct
4 Correct 9 ms 3940 KB Output is correct
5 Correct 8 ms 3840 KB Output is correct
6 Correct 8 ms 3968 KB Output is correct
7 Correct 6 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 9 ms 3968 KB Output is correct
3 Correct 8 ms 3968 KB Output is correct
4 Correct 9 ms 3940 KB Output is correct
5 Correct 8 ms 3840 KB Output is correct
6 Correct 8 ms 3968 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 253 ms 1804 KB Output is correct
9 Correct 324 ms 7040 KB Output is correct
10 Correct 305 ms 7012 KB Output is correct
11 Correct 280 ms 1756 KB Output is correct
12 Correct 234 ms 2840 KB Output is correct
13 Correct 241 ms 2832 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 9 ms 3968 KB Output is correct
3 Correct 8 ms 3968 KB Output is correct
4 Correct 9 ms 3940 KB Output is correct
5 Correct 8 ms 3840 KB Output is correct
6 Correct 8 ms 3968 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 253 ms 1804 KB Output is correct
9 Correct 324 ms 7040 KB Output is correct
10 Correct 305 ms 7012 KB Output is correct
11 Correct 280 ms 1756 KB Output is correct
12 Correct 234 ms 2840 KB Output is correct
13 Correct 241 ms 2832 KB Output is correct
14 Correct 266 ms 7008 KB Output is correct
15 Correct 293 ms 6904 KB Output is correct
16 Correct 269 ms 6848 KB Output is correct
17 Correct 259 ms 7012 KB Output is correct
18 Correct 253 ms 7004 KB Output is correct