oj.uz

Submission #320213

# Submission time Handle Problem Language Result Execution time Memory
320213 2020-11-08T00:45:15 Z caoash Simple game (IZhO17_game) C++17
100 / 100
 76 ms 7032 KB 
#include <bits/stdc++.h> 
using namespace std;

using ll = long long;

using vi = vector<int>;
using vl = vector<ll>;
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define lb lower_bound
#define ub upper_bound

using pi = pair<int,int>;
#define f first
#define s second
#define mp make_pair

const int MX = 1000005;
const int MOD = (int) (1e9 + 7);
const ll INF = (ll) 1e18;

template<class T, int SZ> struct BIT {
    T bit[SZ + 1];
    void upd(int p, int x) {
        for (; p <= SZ; p += (p & -p)) bit[p] += x;
    }
    T sum(int r) {
        T res = 0;
        for (; r; r -= (r & -r)) res += bit[r];
        return res;
    }
    T query(int l, int r) {
        return sum(r) - sum(l - 1); 
    }
};

BIT<int, MX> orz;

void upd(int l, int r, int x) {
    l++, r++;
    orz.upd(l, x);
    orz.upd(r + 1, -x);
}

int qry(int i) {
    i++;
    return orz.sum(i);
}

int main(){
#ifdef mikey 
    freopen("a.in", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m; cin >> n >> m;
    vi a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    auto relax = [&] (int i, int x) {
        int l = a[i], r = a[i + 1];
        if (l > r) swap(l, r);
        upd(l, r, x);
    };
    for (int i = 0; i < n - 1; i++) {
        relax(i, 1);
    }
    for (int i = 0; i < m; i++) {
        int qt; cin >> qt;
        if (qt == 1) {
            int j, v; cin >> j >> v;     
            j--;
            {
                if (j != 0) relax(j - 1, -1);
                if (j != n - 1) relax(j, -1);
            }
            a[j] = v;
            {
                if (j != 0) relax(j - 1, 1);
                if (j != n - 1) relax(j, 1);
            }
        } else {
            int x; cin >> x; 
            cout << qry(x) << '\n';
        }
    }
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 4204 KB Output is correct
3 Correct 3 ms 4076 KB Output is correct
4 Correct 3 ms 4076 KB Output is correct
5 Correct 3 ms 4076 KB Output is correct
6 Correct 3 ms 4076 KB Output is correct
7 Correct 2 ms 364 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 3 ms 4204 KB Output is correct
3 Correct 3 ms 4076 KB Output is correct
4 Correct 3 ms 4076 KB Output is correct
5 Correct 3 ms 4076 KB Output is correct
6 Correct 3 ms 4076 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 40 ms 1764 KB Output is correct
9 Correct 55 ms 6884 KB Output is correct
10 Correct 51 ms 6884 KB Output is correct
11 Correct 42 ms 1772 KB Output is correct
12 Correct 44 ms 2916 KB Output is correct
13 Correct 58 ms 2916 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 3 ms 4204 KB Output is correct
3 Correct 3 ms 4076 KB Output is correct
4 Correct 3 ms 4076 KB Output is correct
5 Correct 3 ms 4076 KB Output is correct
6 Correct 3 ms 4076 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 40 ms 1764 KB Output is correct
9 Correct 55 ms 6884 KB Output is correct
10 Correct 51 ms 6884 KB Output is correct
11 Correct 42 ms 1772 KB Output is correct
12 Correct 44 ms 2916 KB Output is correct
13 Correct 58 ms 2916 KB Output is correct
14 Correct 67 ms 6884 KB Output is correct
15 Correct 70 ms 7032 KB Output is correct
16 Correct 68 ms 7012 KB Output is correct
17 Correct 71 ms 6880 KB Output is correct
18 Correct 76 ms 6884 KB Output is correct