Submission #290313

#	Time	Username	Problem	Language	Result	Execution time	Memory
290313		MasterTaster	Simple game (IZhO17_game)	C++14	100 / 100	77 ms	7036 KiB

game

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int, int>
#define xx first
#define yy second
#define endl "\n"
#define MAXN 1000007

int n, m, arr[100010], bit[1000010];

void upd(int x, int v)
{
    while(x<MAXN)
    {
        bit[x]+=v;
        x+=x&(-x);
    }
}
int sum(int x)
{
    int suma=0;
    while (x)
    {
        suma+=bit[x];
        x-=x&(-x);
    }
    return suma;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin>>n>>m;

    for (int i=0; i<n; i++) cin>>arr[i];

    for (int i=1; i<n; i++)
    {
        upd(min(arr[i], arr[i-1]), 1);
        upd(max(arr[i], arr[i-1])+1, -1);
    }

    while (m--)
    {
        int q; cin>>q;
        if (q==1)
        {
            int i, x; cin>>i>>x;
            i--;
            if (i!=0)
            {
                upd(min(arr[i], arr[i-1]), -1);
                upd(max(arr[i], arr[i-1])+1, 1);

                upd(min(x, arr[i-1]), 1);
                upd(max(x, arr[i-1])+1, -1);
            }
            if (i!=n-1)
            {
                upd(min(arr[i], arr[i+1]), -1);
                upd(max(arr[i], arr[i+1])+1, 1);

                upd(min(x, arr[i+1]), 1);
                upd(max(x, arr[i+1])+1, -1);
            }
            arr[i]=x;
        }
        else
        {
            int h; cin>>h;
            cout<<sum(h)<<endl;
        }
    }
}

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