oj.uz

Submission #672928

# Submission time Handle Problem Language Result Execution time Memory
672928 2022-12-19T03:42:31 Z Alihan_8 Simple game (IZhO17_game) C++17
100 / 100
 315 ms 36104 KB 
#include <bits/stdc++.h>
// include <ext/pb_ds/assoc_container.hpp>
// include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
// define ordered_set tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>
#define mpr make_pair
#define ln '\n'
void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
#define int long long
const int N = 1e6+1;
int T[N*4], lazy[N*4];
void push(int v, int l, int r){
    if ( !lazy[v] ) return;
    if ( l != r ){
        lazy[v*2] += lazy[v];
        lazy[v*2+1] += lazy[v];
    }
    T[v] += (r-l+1)*lazy[v];
    lazy[v] = 0;
}
void upd(int v, int l, int r, int tl, int tr, int val){
    push(v, l, r);
    if ( l > tr or tl > r ) return;
    if ( tl <= l and tr >= r ){
        lazy[v] += val;
        push(v, l, r);
        return;
    }
    int md = (l+r)>>1;
    upd(v*2, l, md, tl, tr, val), upd(v*2+1, md+1, r, tl, tr, val);
    T[v] = T[v*2]+T[v*2+1];
}
int get(int v, int l, int r, int pos){
    push(v, l, r);
    if ( l == r ) return T[v];
    int md = (l+r)>>1;
    if ( pos <= md ) return get(v*2, l, md, pos);
    return get(v*2+1, md+1, r, pos);
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q; cin >> n >> q;
    vector <int> p(n);
    for ( auto &i: p ) cin >> i;
    auto modify = [&](int l, int r, int add){
        if ( min(l, r) < 0 or max(l, r) >= n ) return;
        l = p[l], r = p[r];
        if ( l > r ) swap(l, r);
        upd(1, 1, N-1, l, r, add);
    };
    for ( int i = 1; i < n; i++ ) modify(i-1, i, 1);
    while ( q-- ){
        int t; cin >> t;
        if ( t == 1 ){
            int pos, val; cin >> pos >> val;
            pos--;
            modify(pos, pos-1, -1), modify(pos, pos+1, -1);
            p[pos] = val;
            modify(pos, pos-1, 1), modify(pos, pos+1, 1);
        }
        else{
            int x; cin >> x;
            cout << get(1, 1, N-1, x) << ln;
        }
    }

    cout << '\n';
}

Compilation message

game.cpp: In function 'void IO(std::string)':
game.cpp:11:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
game.cpp:11:70: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 14 ms 24544 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 13 ms 24148 KB Output is correct
5 Correct 14 ms 24368 KB Output is correct
6 Correct 13 ms 24444 KB Output is correct
7 Correct 9 ms 18900 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 14 ms 24544 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 13 ms 24148 KB Output is correct
5 Correct 14 ms 24368 KB Output is correct
6 Correct 13 ms 24444 KB Output is correct
7 Correct 9 ms 18900 KB Output is correct
8 Correct 53 ms 2080 KB Output is correct
9 Correct 154 ms 36088 KB Output is correct
10 Correct 164 ms 36104 KB Output is correct
11 Correct 45 ms 1996 KB Output is correct
12 Correct 85 ms 4132 KB Output is correct
13 Correct 73 ms 35996 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 14 ms 24544 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 13 ms 24148 KB Output is correct
5 Correct 14 ms 24368 KB Output is correct
6 Correct 13 ms 24444 KB Output is correct
7 Correct 9 ms 18900 KB Output is correct
8 Correct 53 ms 2080 KB Output is correct
9 Correct 154 ms 36088 KB Output is correct
10 Correct 164 ms 36104 KB Output is correct
11 Correct 45 ms 1996 KB Output is correct
12 Correct 85 ms 4132 KB Output is correct
13 Correct 73 ms 35996 KB Output is correct
14 Correct 315 ms 35992 KB Output is correct
15 Correct 306 ms 35920 KB Output is correct
16 Correct 311 ms 36016 KB Output is correct
17 Correct 302 ms 36004 KB Output is correct
18 Correct 314 ms 35920 KB Output is correct