Submission #107723

#	Time	Username	Problem	Language	Result	Execution time	Memory
107723		Shafin666	Simple game (IZhO17_game)	C++14	100 / 100	324 ms	7040 KiB

game

#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 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51