oj.uz

Submission #93566

# Submission time Handle Problem Language Result Execution time Memory
93566 2019-01-09T16:28:38 Z Turysbek Simple game (IZhO17_game) C++14
0 / 100
 8 ms 7420 KB 
// In the Name of God

#include <bits/stdc++.h>

using namespace std;

#define	ll long long
#define ull unsigned long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define sz(a) int(a.size())
#define all(v) v.begin(), v.end()
#define bpc(v) __builtin_popcountll(v)
#define itr iterator
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define per(i, a, b) for (int i = a; i >= b; --i)
#define ub upper_bound
#define lb lower_bound

const int N = 1e5 + 5;
const int mod = 1e8 + 7;
const int inf = 1e6 + 1;
const double eps = 1e-15;
const int pw = 257;

int n, m, a[N], t[inf * 4];

void upd(int v, int l, int r, int pos, int val) {
    if (l == r) {
        t[v] += val;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid)
        upd(v + v, l, mid, pos, val);
    else
        upd(v + v + 1, mid + 1, r, pos, val);
    t[v] = t[v + v] + t[v + v + 1];
}

int get(int v, int l, int r, int L, int R) {
    if (L > r || l > R)
        return 0;
    if (L <= l && r <= R)
        return t[v];
    int mid = (l + r) >> 1;
    return get(v + v, l, mid, L, R) + get(v + v + 1, mid + 1, r, L, R);
}

int main() {
	#ifdef Madi
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
	#endif

	ios_base :: sync_with_stdio(false); cin.tie(NULL);

    cin >> n >> m;
    rep(i, 1, n) {
        cin >> a[i];
        upd(1, 1, inf, a[i], 1);
    }

    rep(i, 1, m) {
        int type;
        cin >> type;
        if (type == 1) {
            int pos, val;
            cin >> pos >> val;
            upd(1, 1, inf, a[pos], -1);
            a[pos] = val;
            upd(1, 1, inf, a[pos], 1);
        }
        else {
            int x;
            cin >> x;
            cout << get(1, 1, inf, 1, x) << "\n";
        }
    }

	#ifdef Madi
    cerr << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    #endif
	return 0;
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 8 ms 7420 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 8 ms 7420 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 8 ms 7420 KB Output isn't correct
3 Halted 0 ms 0 KB -