oj.uz

Submission #1103028

# Submission time Handle Problem Language Result Execution time Memory
1103028 2024-10-19T12:20:48 Z Zero_OP Simple game (IZhO17_game) C++14
100 / 100
 153 ms 17992 KB 
#include <bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for(int i = (l), _r = (r); i < _r; ++i)
#define FOR(i, l, r) for(int i = (l), _r = (r); i <= _r; ++i)
#define ROF(i, r, l) for(int i = (r), _l = (l); i >= _l; --i)
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()
#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
bool minimize(T& a, const T& b){
    if(a > b) return a = b, true; return false;
}

template<typename T>
bool maximize(T& a, const T& b){
    if(a < b) return a = b, true; return false;
}

using ll = long long;
using ld = long double;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T> T random_int(T l, T r){ return uniform_int_distribution<T>(l, r)(rng); }
template<typename T> T random_real(T l, T r){ return uniform_real_distribution<T>(l, r)(rng); }

struct SegmentTree{
    vector<int> lazy;
    SegmentTree(int n) : lazy(n << 2) {}

    void apply(int id, int l, int r, int val){
        lazy[id] += val;
    }

    void lazyDown(int id, int l, int r, int mid){
        if(lazy[id] != 0){
            apply(id << 1, l, mid, lazy[id]);
            apply(id << 1 | 1, mid + 1, r, lazy[id]);
            lazy[id] = 0;
        }
    }

    void update(int id, int l, int r, int u, int v, int val){
        if(u <= l && r <= v) apply(id, l, r, val);
        else{
            int mid = l + r >> 1;
            lazyDown(id, l, r, mid);
            if(u <= mid) update(id << 1, l, mid, u, v, val);
            if(mid < v) update(id << 1 | 1, mid + 1, r, u, v, val);
        }
    }

    int query(int id, int l, int r, int pos){
        if(l == r) return lazy[id];
        int mid = l + r >> 1;
        lazyDown(id, l, r, mid);
        if(pos <= mid) return query(id << 1, l, mid, pos);
        else return query(id << 1 | 1, mid + 1, r, pos);
    }
};

void testcase(){
    int n, m;
    cin >> n >> m;

    vector<int> a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }

    SegmentTree T(1e6);
    int bound = 1e6;

    auto upd = [&](int l, int r, int val){
        if(l > r) swap(l, r);
        T.update(1, 1, bound, l, r, val);
    };

    for(int i = 1; i < n; ++i){
        upd(a[i - 1], a[i], +1);
    }

    while(m--){
        int type;
        cin >> type;
        if(type == 1){
            int pos, val;
            cin >> pos >> val;
            --pos;
            if(pos > 0) upd(a[pos - 1], a[pos], -1);
            if(pos < n - 1) upd(a[pos], a[pos + 1], -1);
            a[pos] = val;
            if(pos > 0) upd(a[pos - 1], a[pos], +1);
            if(pos < n - 1) upd(a[pos], a[pos + 1], +1);
        } else{
            int H;
            cin >> H;
            cout << T.query(1, 1, bound, H) << '\n';
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    #define filename "task"
    if(fopen(filename".inp", "r")){
        freopen(filename".inp", "r", stdin);
        freopen(filename".out", "w", stdout);
    }

    int T = 1; //cin >> T;
    while(T--) testcase();

    return 0;
}

Compilation message

game.cpp: In function 'bool minimize(T&, const T&)':
game.cpp:15:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   15 |     if(a > b) return a = b, true; return false;
      |     ^~
game.cpp:15:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   15 |     if(a > b) return a = b, true; return false;
      |                                   ^~~~~~
game.cpp: In function 'bool maximize(T&, const T&)':
game.cpp:20:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   20 |     if(a < b) return a = b, true; return false;
      |     ^~
game.cpp:20:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   20 |     if(a < b) return a = b, true; return false;
      |                                   ^~~~~~
game.cpp: In member function 'void SegmentTree::update(int, int, int, int, int, int)':
game.cpp:49:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |             int mid = l + r >> 1;
      |                       ~~^~~
game.cpp: In member function 'int SegmentTree::query(int, int, int, int)':
game.cpp:58:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |         int mid = l + r >> 1;
      |                   ~~^~~
game.cpp: In function 'int main()':
game.cpp:112:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |         freopen(filename".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
game.cpp:113:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         freopen(filename".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15952 KB Output is correct
2 Correct 5 ms 15952 KB Output is correct
3 Correct 4 ms 15952 KB Output is correct
4 Correct 6 ms 15952 KB Output is correct
5 Correct 5 ms 15952 KB Output is correct
6 Correct 5 ms 15952 KB Output is correct
7 Correct 3 ms 15952 KB Output is correct
8 Correct 30 ms 16704 KB Output is correct
9 Correct 76 ms 17992 KB Output is correct
10 Correct 68 ms 16968 KB Output is correct
11 Correct 26 ms 16464 KB Output is correct
12 Correct 53 ms 16968 KB Output is correct
13 Correct 39 ms 17900 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15952 KB Output is correct
2 Correct 5 ms 15952 KB Output is correct
3 Correct 4 ms 15952 KB Output is correct
4 Correct 6 ms 15952 KB Output is correct
5 Correct 5 ms 15952 KB Output is correct
6 Correct 5 ms 15952 KB Output is correct
7 Correct 3 ms 15952 KB Output is correct
8 Correct 30 ms 16704 KB Output is correct
9 Correct 76 ms 17992 KB Output is correct
10 Correct 68 ms 16968 KB Output is correct
11 Correct 26 ms 16464 KB Output is correct
12 Correct 53 ms 16968 KB Output is correct
13 Correct 39 ms 17900 KB Output is correct
14 Correct 153 ms 17332 KB Output is correct
15 Correct 138 ms 16712 KB Output is correct
16 Correct 146 ms 17992 KB Output is correct
17 Correct 148 ms 17872 KB Output is correct
18 Correct 139 ms 17992 KB Output is correct