Submission #38348

#	Time	Username	Problem	Language	Result	Execution time	Memory
38348		antimirage	Simple game (IZhO17_game)	C++14	100 / 100	559 ms	37172 KiB

game

#include <iostream>
#include <vector>
#include <deque>
#include <math.h>
#include <set>
#include <iomanip>
#include <time.h>
#include <list>
#include <stdio.h>
#include <queue>
#include <map>
#include <algorithm>
#include <assert.h>
#include <memory.h>

#define mk make_pair
#define sc second
#define fr first
#define pb emplace_back
#define all(s) s.begin(), s.end()
#define sz(s) ( (int)s.size() )

using namespace std;

const int N = 1e6 + 5;

int n, m, ar[N], mx = 1e6;

struct st
{
    int sum, val;
};

st t[N * 4];

void push (int v, int tl, int tr)
{
    t[v].val += t[v].sum * (tr - tl + 1);

    if (tl != tr)
    {
        t[v + v].sum += t[v].sum;
        t[v + v + 1].sum += t[v].sum;
    }

    t[v].sum = 0;
}

void update (int l, int r, int val, int v = 1, int tl = 1, int tr = mx)
{
    push(v, tl, tr);

    if (l > tr || tl > r)
        return ;

    if ( l <= tl && tr <= r )
    {
        t[v].sum += val;
        push(v, tl, tr);
        return ;
    }
    int tm = (tl + tr) >> 1;

    update ( l, r, val, v + v, tl, tm );
    update ( l, r, val, v + v + 1, tm +  1, tr );

    t[v].val = t[v + v].val + t[v + v + 1].val;
}
int get (int pos, int v = 1, int tl = 1, int tr = mx)
{
    push(v, tl, tr);

    if(tl == tr)
        return t[v].val;

    int tm = (tl + tr) >> 1;

    if (pos <= tm)
        return get(pos, v + v, tl, tm);

    return get(pos, v + v + 1, tm + 1, tr);
}

char type;

int pos, val;

main ()
{
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &ar[i]);
        if (i > 1)
            update ( min( ar[i - 1], ar[i] ), max( ar[i - 1], ar[i] ), 1 );
    }
    while (m--)
    {
        scanf("\n%c", &type);
        if (type == '1')
        {
            scanf("%d%d", &pos, &val);
            if (pos > 1)
                update ( min( ar[pos - 1], ar[pos] ), max( ar[pos - 1], ar[pos] ), -1 );
            if (pos < n)
                update ( min( ar[pos + 1], ar[pos] ), max( ar[pos + 1], ar[pos] ), -1 );

            ar[pos] = val;

            if (pos > 1)
                update ( min( ar[pos - 1], ar[pos] ), max( ar[pos - 1], ar[pos] ), 1 );
            if (pos < n)
                update ( min( ar[pos + 1], ar[pos] ), max( ar[pos + 1], ar[pos] ), 1 );
        }
        else
        {
            scanf("%d", &pos);
            printf("%d\n", get(pos) );
        }
    }
}

Compilation message (stderr)

game.cpp:88:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main ()
       ^
game.cpp: In function 'int main()':
game.cpp:94:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &ar[i]);
                            ^
game.cpp:100:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("\n%c", &type);
                             ^
game.cpp:103:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &pos, &val);
                                      ^
game.cpp:118:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &pos);
                              ^

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