Submission #624104

#	Time	Username	Problem	Language	Result	Execution time	Memory
624104		Hanksburger	Simple game (IZhO17_game)	C++17	100 / 100	57 ms	6844 KiB

game

#include <bits/stdc++.h>
using namespace std;
int bit[1000005], a[100005];
void update(int x, int y)
{
    for (int i=x; i<=1e6; i+=i&(-i))
        bit[i]+=y;
}
int query(int x)
{
    int ans=0;
    for (int i=x; i; i-=i&(-i))
        ans+=bit[i];
    return ans;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i=1; i<=n; i++)
    {
        cin >> a[i];
        if (i>=2)
        {
            update(min(a[i-1], a[i]), 1);
            update(max(a[i-1], a[i]), -1);
        }
    }
    for (int i=1; i<=m; i++)
    {
        int t, x, y;
        cin >> t >> x;
        if (t==1)
        {
            cin >> y;
            if (x>=2)
            {
                update(min(a[x-1], a[x]), -1);
                update(max(a[x-1], a[x]), 1);
            }
            if (x<n)
            {
                update(min(a[x], a[x+1]), -1);
                update(max(a[x], a[x+1]), 1);
            }
            a[x]=y;
            if (x>=2)
            {
                update(min(a[x-1], a[x]), 1);
                update(max(a[x-1], a[x]), -1);
            }
            if (x<n)
            {
                update(min(a[x], a[x+1]), 1);
                update(max(a[x], a[x+1]), -1);
            }
        }
        else
            cout << query(x) << '\n';
    }
    return 0;
}

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