oj.uz

Submission #883691

# Submission time Handle Problem Language Result Execution time Memory
883691 2023-12-05T17:59:12 Z Sokol080808 Simple game (IZhO17_game) C++17
100 / 100
 41 ms 6860 KB 
#ifdef ONPC
    #define _GLIBCXX_DEBUG
#endif

#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <malloc.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using ll = long long;
using ull = unsigned long long;
using ld = long double;

template<typename T1, typename T2> istream& operator>>(istream& in, pair<T1, T2>& p) {in >> p.first >> p.second; return in;}
template<typename T1, typename T2> ostream& operator<<(ostream& out, pair<T1, T2>& p) {out << p.first << ' ' << p.second; return out;}
template<typename T> istream& operator>>(istream& in, vector<T>& v) {for (auto& x : v) in >> x; return in;}
template<typename T> ostream& operator<<(ostream& out, vector<T>& v) {for (auto& x : v) out << x << ' '; return out;}
template<typename T> ostream& operator<<(ostream& out, set<T>& v) {for (auto& x : v) out << x << ' '; return out;}
template<typename T> ostream& operator<<(ostream& out, multiset<T>& v) {for (auto& x : v) out << x << ' '; return out;}

const int MAX_INT = 2147483647;
const double pi = acos(-1.0);
const int mod = 1e9 + 7;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

struct Fenwick {
    vector<int> t;
    int SIZE;

    Fenwick(int n): SIZE(n) {
        t.assign(SIZE, 0);
    }

    int sum(int ind) {
        int res = 0;
        for (int i = ind; i < SIZE; i = (i | (i + 1))) res += t[i];
        return res;
    }

    void inc(int r, ll delta) {
        ll res = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1) t[r] +=delta;
    }

    void inc(int l, int r, int delta) {
        inc(r, delta);
        inc(l - 1, -delta);
    }
};

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<int> h(n);
    for (int i = 0; i < n; i++) cin >> h[i];

    Fenwick f(1000001);

    auto add = [&](int x, int y) {
        if (x > y) swap(x, y);
        f.inc(x, y, 1);
    };

    auto del = [&](int x, int y) {
        if (x > y) swap(x, y);
        f.inc(x, y, -1);
    };

    for (int i = 0; i + 1 < n; i++) add(h[i], h[i + 1]);

    for (int i = 0; i < m; i++) {
        int t;
        cin >> t;
        if (t == 1) {
            int id, nh;
            cin >> id >> nh;
            id--;
            if (id - 1 >= 0) del(h[id - 1], h[id]);
            if (id + 1 < n) del(h[id], h[id + 1]);
            h[id] = nh;
            if (id - 1 >= 0) add(h[id - 1], h[id]);
            if (id + 1 < n) add(h[id], h[id + 1]);
        } else {
            int H;
            cin >> H;
            cout << f.sum(H) << '\n';
        }
    }

    return 0;
}

Compilation message

game.cpp: In member function 'void Fenwick::inc(int, ll)':
game.cpp:53:12: warning: unused variable 'res' [-Wunused-variable]
   53 |         ll res = 0;
      |            ^~~

Subtask #1
22.0 / 22.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4188 KB Output is correct
2 Correct 2 ms 4188 KB Output is correct
3 Correct 2 ms 4440 KB Output is correct
4 Correct 2 ms 4188 KB Output is correct
5 Correct 2 ms 4188 KB Output is correct
6 Correct 2 ms 4188 KB Output is correct
7 Correct 1 ms 4188 KB Output is correct
8 Correct 22 ms 5724 KB Output is correct
9 Correct 31 ms 6860 KB Output is correct
10 Correct 31 ms 6740 KB Output is correct
11 Correct 22 ms 5592 KB Output is correct
12 Correct 32 ms 6736 KB Output is correct
13 Correct 26 ms 6736 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4188 KB Output is correct
2 Correct 2 ms 4188 KB Output is correct
3 Correct 2 ms 4440 KB Output is correct
4 Correct 2 ms 4188 KB Output is correct
5 Correct 2 ms 4188 KB Output is correct
6 Correct 2 ms 4188 KB Output is correct
7 Correct 1 ms 4188 KB Output is correct
8 Correct 22 ms 5724 KB Output is correct
9 Correct 31 ms 6860 KB Output is correct
10 Correct 31 ms 6740 KB Output is correct
11 Correct 22 ms 5592 KB Output is correct
12 Correct 32 ms 6736 KB Output is correct
13 Correct 26 ms 6736 KB Output is correct
14 Correct 41 ms 6740 KB Output is correct
15 Correct 40 ms 6748 KB Output is correct
16 Correct 40 ms 6740 KB Output is correct
17 Correct 40 ms 6748 KB Output is correct
18 Correct 41 ms 6772 KB Output is correct