oj.uz

Submission #855344

# Submission time Handle Problem Language Result Execution time Memory
855344 2023-10-01T06:46:53 Z Alfraganus Simple game (IZhO17_game) C++17
100 / 100
 149 ms 11228 KB 
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define ll long long
#define fs first
#define ss second
#define all(a) a.begin(), a.end()
#define print(a)          \
    for (auto x : a)      \
        cout << x << ' '; \
    cout << endl;

#define printmp(a)   \
    for (auto x : a) \
        cout << x.fs << ' ' << x.ss << endl;

struct SegTree
{
    int size = 1;
    vector<int> sums;

    SegTree (){
        while(1e6 > size)
            size <<= 1;
        sums.resize(size << 1);
    }

    void add(int l, int r, int i, int x, int lx, int rx){
        if(l <= lx and rx <= r){
            sums[x] += i;
            return;
        }
        if(r <= lx or rx <= l)
            return;
        int m = (lx + rx) >> 1;
        add(l, r, i, (x << 1) + 1, lx, m);
        add(l, r, i, (x << 1) + 2, m, rx);
    }

    void add(int l, int r, int i){
        if(l > r)
            swap(l, r);
        add(l, r, i, 0, 0, size);
    }

    int ans(int h, int x, int lx, int rx){
        if(rx == lx + 1)
            return sums[x];
        int m = (lx + rx) >> 1;
        if(h < m)
            return sums[x] + ans(h, (x << 1) + 1, lx, m);
        else
            return sums[x] + ans(h, (x << 1) + 2, m, rx);
    }

    int ans(int h){
        return ans(h, 0, 0, size);
    }
};


void solve()
{
    int n, m;
    cin >> n >> m;
    vector<int> h(n);
    for(int i = 0; i < n; i ++)
        cin >> h[i];
    SegTree s;
    for(int i = 1; i < n; i ++)
        s.add(h[i - 1], h[i], 1);
    while(m --){
        int type;
        cin >> type;
        if(type == 1){
            int i, v;
            cin >> i >> v;
            if(n == 1)
                continue;
            if(i == 1){
                s.add(h[i], h[i - 1], -1);
                h[i - 1] = v;
                s.add(h[i], h[i - 1], 1);
            }
            else if(i == n){
                s.add(h[i - 2], h[i - 1], -1);
                h[i - 1] = v;
                s.add(h[i - 2], h[i - 1], 1);
            }
            else{
                s.add(h[i], h[i - 1], -1);
                s.add(h[i], v, 1);
                s.add(h[i - 2], h[i - 1], -1);
                h[i - 1] = v;
                s.add(h[i - 2], h[i - 1], 1);
            }
        }
        else{
            int h;
            cin >> h;
            if(n == 1){
                cout << 0 << endl;
                continue;
            }
            cout << s.ans(h) << endl;
        }
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    // freopen("game.in", "r", stdin);
    // freopen("game.out", "w", stdout);
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
        cout << endl;
    }
}

Subtask #1
22.0 / 22.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 3 ms 8496 KB Output is correct
3 Correct 3 ms 8540 KB Output is correct
4 Correct 3 ms 8540 KB Output is correct
5 Correct 3 ms 8540 KB Output is correct
6 Correct 3 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 29 ms 9812 KB Output is correct
9 Correct 62 ms 11088 KB Output is correct
10 Correct 65 ms 11180 KB Output is correct
11 Correct 27 ms 9820 KB Output is correct
12 Correct 51 ms 11020 KB Output is correct
13 Correct 47 ms 10960 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 3 ms 8496 KB Output is correct
3 Correct 3 ms 8540 KB Output is correct
4 Correct 3 ms 8540 KB Output is correct
5 Correct 3 ms 8540 KB Output is correct
6 Correct 3 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 29 ms 9812 KB Output is correct
9 Correct 62 ms 11088 KB Output is correct
10 Correct 65 ms 11180 KB Output is correct
11 Correct 27 ms 9820 KB Output is correct
12 Correct 51 ms 11020 KB Output is correct
13 Correct 47 ms 10960 KB Output is correct
14 Correct 149 ms 11216 KB Output is correct
15 Correct 116 ms 11088 KB Output is correct
16 Correct 122 ms 11088 KB Output is correct
17 Correct 126 ms 11204 KB Output is correct
18 Correct 130 ms 11228 KB Output is correct