Submission #1128426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128426		_Temirhan	Simple game (IZhO17_game)	C++20	100 / 100	350 ms	34628 KiB

game

#include <bits/stdc++.h>

using namespace std;
  
#define int long long
#define pb push_back
#define sz(x) x.size()
#define F first
#define S second
#define nl '\n'

void Tima() 
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
}  

const int N = 1e6 + 1;
const int inf = 1e12;
const int mod = 1e9 + 7;
int n, q, a[N], t[4 * N], add[4 * N];

void push( int v, int tl, int tr )
{
    if( add[v] == 0 )
        return;
    t[v] += add[v] * (tr - tl + 1);
    if( tl < tr )
    {
        add[v + v] += add[v];
        add[v + v + 1] += add[v];
    }
    add[v] = 0;
}

void upd( int v, int tl, int tr, int l, int r, int x )
{
    push(v, tl, tr);
    if( tl > r || l > tr )
        return;
    if( l <= tl && tr <= r )
    {
        add[v] += x;
        push(v, tl, tr);
        return;
    }
    int m = (tl + tr) / 2;
    upd(v + v, tl, m, l, r, x);
    upd(v + v + 1, m + 1, tr, l, r, x);
}

int get( int v, int tl, int tr, int p )
{
    push(v, tl, tr);
    if( tl == tr )
        return t[v];
    int m = (tl + tr) / 2;
    if( p <= m )
        return get(v + v, tl, m, p);
    else
        return get(v + v + 1, m + 1, tr, p);
}

signed main() 
{
    // Tima();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >>n >>q;
    for( int i = 1; i <= n; ++i )
    {
        cin >>a[i];
        if( i > 1 )
            upd(1, 1, N - 1, min(a[i - 1], a[i]), max(a[i - 1], a[i]), 1);
    }
    while( q-- )
    {
        int type, i, val, h;
        cin >>type;
        if( type == 1 )
        {
            cin >>i >>val;
            if( i > 1 )
            {
                upd(1, 1, N - 1, min(a[i - 1], a[i]), max(a[i - 1], a[i]), -1);
                upd(1, 1, N - 1, min(a[i - 1], val), max(a[i - 1], val), 1);
            }
            if( i < n )
            {
                upd(1, 1, N - 1, min(a[i], a[i + 1]), max(a[i], a[i + 1]), -1);
                upd(1, 1, N - 1, min(val, a[i + 1]), max(val, a[i + 1]), 1);
            }
            a[i] = val;
        }
        else
        {
            cin >>h;
            cout <<get(1, 1, N - 1, h) <<nl;
        }
    }
}

Compilation message (stderr)

game.cpp: In function 'void Tima()':
game.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
game.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51