oj.uz

Submission #896822

# Submission time Handle Problem Language Result Execution time Memory
896822 2024-01-02T09:03:50 Z raul2008487 Simple game (IZhO17_game) C++17
100 / 100
 241 ms 66016 KB 
#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define pb push_back
#define eb emplace_back
#define vl vector<ll>
#define fi first
#define se second
#define in insert
#define mpr make_pair
#define lg(x) __lg(x)
#define bpc(x) __builtin_popcount(x)
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;
const int mod = 998244353;
const int sz = 3e5+5; /// mind the sz
/*struct BIT{
    vl e;
    void init(ll n){
        e.assign(n+1, -1);
    }
    ll base(ll x){
        if(e[x] < 0){
            return x;
        }
        return e[x] = base(e[x]);
    }
    bool unite(ll a, ll b){
        a = base(a);
        b = base(b);
        if(a == b){return false;}
        if(e[a] > e[b]){swap(a, b);}
    }
};*/
struct Segtree{
    vl st, lazy;
    void init(ll n){
        st.assign(n << 2, 0);
        lazy.assign(n << 2, 0);
    }
    void push(ll v, ll l, ll r){
        if(l == r || !lazy[v]){return ;}
        lazy[v*2] += lazy[v];
        lazy[v*2+1] += lazy[v];
        ll m = (l + r) >> 1;
        st[v*2] += ((m - l + 1) * lazy[v]);
        st[v*2+1] += ((r - m) * lazy[v]);
        lazy[v] = 0;
    }
    void update(ll v, ll tl, ll tr, ll l, ll r, ll val){
        if(tl > r || tr < l){return ;}
        if(tl >= l && tr <= r){
            lazy[v] += val;
            st[v] += ((tr - tl + 1) * val);
            return ;
        }
        push(v, tl, tr);
        ll tm = (tl + tr) >> 1;
        update(v*2, tl, tm, l, r, val);
        update(v*2+1, tm+1, tr, l, r, val);
        st[v] = st[v*2] + st[v * 2 + 1];
    }
    ll get(ll v, ll tl, ll tr, ll pos){
        if(tl > pos || tr < pos){return 0;}
        if(tl == tr){
            return st[v];
        }
        push(v, tl, tr);
        ll tm = (tl + tr)>>1;
        if(pos <= tm){
            return get(v*2, tl, tm, pos);
        }
        else{
            return get(v*2+1, tm + 1, tr, pos);
        }
    }
};
void solve()
{
    Segtree st;
    ll n, m, i, j, type, l, r, pos, val, N = 1e6;
    cin>>n>>m;
    st.init(N);
    vl h(n+1);
    for(i=1;i<=n;i++){
        cin>>h[i];
    }
    for(i=1;i<n;i++){
        st.update(1, 1, N, min(h[i], h[i+1]), max(h[i], h[i+1]), 1);
    }
    for(i=1;i<=m;i++){
        cin>>type;
        if(type == 1){
            cin >> pos >> val;
            if(pos > 1){
                st.update(1, 1, N, min(h[pos], h[pos-1]), max(h[pos], h[pos-1]), -1);
                st.update(1, 1, N, min(val, h[pos-1]), max(val, h[pos-1]), 1);
            }
            if(pos != n){
                st.update(1, 1, N, min(h[pos], h[pos+1]), max(h[pos], h[pos+1]), -1);
                st.update(1, 1, N, min(val, h[pos + 1]), max(val, h[pos + 1]), 1);
                }
            h[pos] = val;
        }
        else{
            cin >> pos;
            cout << st.get(1, 1, N, pos) << endl;
        }
    }
 
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //precomp();
    ll tst=1;
    //cin>>tst;
    while(tst--){
            solve();
    }
}
/*
3 3
1 5 1
2 3
1 1 5
2 3
ok.
*/

Compilation message

game.cpp: In function 'void solve()':
game.cpp:82:17: warning: unused variable 'j' [-Wunused-variable]
   82 |     ll n, m, i, j, type, l, r, pos, val, N = 1e6;
      |                 ^
game.cpp:82:26: warning: unused variable 'l' [-Wunused-variable]
   82 |     ll n, m, i, j, type, l, r, pos, val, N = 1e6;
      |                          ^
game.cpp:82:29: warning: unused variable 'r' [-Wunused-variable]
   82 |     ll n, m, i, j, type, l, r, pos, val, N = 1e6;
      |                             ^

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 63068 KB Output is correct
2 Correct 13 ms 62912 KB Output is correct
3 Correct 17 ms 63320 KB Output is correct
4 Correct 13 ms 63068 KB Output is correct
5 Correct 14 ms 63116 KB Output is correct
6 Correct 12 ms 62972 KB Output is correct
7 Correct 10 ms 63068 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 63068 KB Output is correct
2 Correct 13 ms 62912 KB Output is correct
3 Correct 17 ms 63320 KB Output is correct
4 Correct 13 ms 63068 KB Output is correct
5 Correct 14 ms 63116 KB Output is correct
6 Correct 12 ms 62972 KB Output is correct
7 Correct 10 ms 63068 KB Output is correct
8 Correct 48 ms 64832 KB Output is correct
9 Correct 114 ms 65872 KB Output is correct
10 Correct 121 ms 66016 KB Output is correct
11 Correct 43 ms 64652 KB Output is correct
12 Correct 74 ms 65616 KB Output is correct
13 Correct 57 ms 65876 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 63068 KB Output is correct
2 Correct 13 ms 62912 KB Output is correct
3 Correct 17 ms 63320 KB Output is correct
4 Correct 13 ms 63068 KB Output is correct
5 Correct 14 ms 63116 KB Output is correct
6 Correct 12 ms 62972 KB Output is correct
7 Correct 10 ms 63068 KB Output is correct
8 Correct 48 ms 64832 KB Output is correct
9 Correct 114 ms 65872 KB Output is correct
10 Correct 121 ms 66016 KB Output is correct
11 Correct 43 ms 64652 KB Output is correct
12 Correct 74 ms 65616 KB Output is correct
13 Correct 57 ms 65876 KB Output is correct
14 Correct 232 ms 65952 KB Output is correct
15 Correct 219 ms 65876 KB Output is correct
16 Correct 225 ms 65872 KB Output is correct
17 Correct 241 ms 65888 KB Output is correct
18 Correct 218 ms 66008 KB Output is correct