oj.uz

Submission #399958

# Submission time Handle Problem Language Result Execution time Memory
399958 2021-05-07T00:59:15 Z abc864197532 Simple game (IZhO17_game) C++17
100 / 100
 202 ms 6916 KB 
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define info() cerr << __PRETTY_FUNCTION__ << ": " << __LINE__ << endl
#define test(args...) info(), abc("[" + string(#args) + "]", args)
void abc() {cerr << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cerr << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.X >> a.Y;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.X << ", " << a.Y << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}
const int N = 1000087, logN = 20, K = 111;

int bit[N];

void add(int p, int v) {
    p += 5;
    for (int i = p; i < N; i += i & (-i)) bit[i] += v;
}

int query(int p) {
    p += 5;
    int ans = 0;
    for (int i = p; i > 0; i -= i & (-i)) ans += bit[i];
    return ans;
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector <int> a(n);
    auto chg = [&](int i, int v) {
        if (i - 1 < 0 || i >= n) return;
        int mn = min(a[i - 1], a[i]), mx = max(a[i - 1], a[i]);
        add(mn + 1, v);
        add(mx, -v);
    };
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        chg(i, 1);
    }
    while (q--) {
        int t, p, x;
        cin >> t >> p;
        if (t == 1) {
            cin >> x, --p;
            chg(p, -1);
            chg(p + 1, -1);
            a[p] = x;
            chg(p, 1);
            chg(p + 1, 1);
        } else {
            cout << query(p) << endl;
        }
    }
}
/*
3 3
1 5 1
2 3
1 1 5
2 3
 */

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 4 ms 4044 KB Output is correct
3 Correct 4 ms 4048 KB Output is correct
4 Correct 4 ms 4044 KB Output is correct
5 Correct 4 ms 4044 KB Output is correct
6 Correct 4 ms 4044 KB Output is correct
7 Correct 3 ms 332 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 4 ms 4044 KB Output is correct
3 Correct 4 ms 4048 KB Output is correct
4 Correct 4 ms 4044 KB Output is correct
5 Correct 4 ms 4044 KB Output is correct
6 Correct 4 ms 4044 KB Output is correct
7 Correct 3 ms 332 KB Output is correct
8 Correct 185 ms 1696 KB Output is correct
9 Correct 202 ms 6816 KB Output is correct
10 Correct 200 ms 6768 KB Output is correct
11 Correct 183 ms 1560 KB Output is correct
12 Correct 188 ms 2784 KB Output is correct
13 Correct 190 ms 2804 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 4 ms 4044 KB Output is correct
3 Correct 4 ms 4048 KB Output is correct
4 Correct 4 ms 4044 KB Output is correct
5 Correct 4 ms 4044 KB Output is correct
6 Correct 4 ms 4044 KB Output is correct
7 Correct 3 ms 332 KB Output is correct
8 Correct 185 ms 1696 KB Output is correct
9 Correct 202 ms 6816 KB Output is correct
10 Correct 200 ms 6768 KB Output is correct
11 Correct 183 ms 1560 KB Output is correct
12 Correct 188 ms 2784 KB Output is correct
13 Correct 190 ms 2804 KB Output is correct
14 Correct 137 ms 6804 KB Output is correct
15 Correct 174 ms 6916 KB Output is correct
16 Correct 138 ms 6724 KB Output is correct
17 Correct 154 ms 6812 KB Output is correct
18 Correct 149 ms 6724 KB Output is correct