Submission #94283

#	Time	Username	Problem	Language	Result	Execution time	Memory
94283		Kastanda	Simple game (IZhO17_game)	C++11	100 / 100	106 ms	10872 KiB

game

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, MXN = 1e6 + 9;
int n, q, A[N], L[MXN], G[MXN];
inline void AddL(int i, int val)
{
    for (i ++; i < MXN; i += i & -i)
        L[i] += val;
}
inline int GetL(int i)
{
    int ret = 0;
    for (i ++; i; i -= i & -i)
        ret += L[i];
    return (ret);
}
inline void AddG(int i, int val)
{
    for (i = MXN - i - 1; i < MXN; i += i & -i)
        G[i] += val;
}
inline int GetG(int i)
{
    int ret = 0;
    for (i = MXN - i - 1; i; i -= i & - i)
        ret += G[i];
    return (ret);
}
int main()
{
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
        scanf("%d", &A[i]);

    for (int i = 1; i < n; i++)
    {
        AddL(max(A[i], A[i + 1]), 1);
        AddG(min(A[i], A[i + 1]), 1);
    }

    for (; q; q --)
    {
        int t, a, b;
        scanf("%d%d", &t, &a);
        if (t == 2)
        {
            printf("%d\n", n - 1 - (GetL(a - 1) + GetG(a + 1)));
            continue;
        }
        scanf("%d", &b);

        if (a > 1)
        {
            AddL(max(A[a], A[a - 1]), -1);
            AddG(min(A[a], A[a - 1]), -1);
        }
        if (a < n)
        {
            AddL(max(A[a], A[a + 1]), -1);
            AddG(min(A[a], A[a + 1]), -1);
        }

        A[a] = b;

        if (a > 1)
        {
            AddL(max(A[a], A[a - 1]), 1);
            AddG(min(A[a], A[a - 1]), 1);
        }
        if (a < n)
        {
            AddL(max(A[a], A[a + 1]), 1);
            AddG(min(A[a], A[a + 1]), 1);
        }
    }
    return 0;
}

Compilation message (stderr)

game.cpp: In function 'int main()':
game.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &q);
     ~~~~~^~~~~~~~~~~~~~~~
game.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &A[i]);
         ~~~~~^~~~~~~~~~~~~
game.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &t, &a);
         ~~~~~^~~~~~~~~~~~~~~~
game.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &b);
         ~~~~~^~~~~~~~~~

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