Submission #1091624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091624		sofija6	Simple game (IZhO17_game)	C++14	100 / 100	51 ms	11344 KiB

game

#include <bits/stdc++.h>
#define ll long long
#define MAXH 1000010
#define MAXN 100010
using namespace std;
ll h[MAXN];
struct bit
{
    vector<ll> sum;
    void Init()
    {
        sum.resize(MAXH);
    }
    void Add(ll pos,ll val)
    {
        for (ll i=pos;i<MAXH;i+=i&(-i))
            sum[i]+=val;
    }
    ll Calc(ll pos)
    {
        ll ans=0;
        for (ll i=pos;i>0;i-=i&(-i))
            ans+=sum[i];
        return ans;
    }
};
bit B;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,m,t,x,y;
    cin >> n >> m;
    B.Init();
    for (ll i=1;i<=n;i++)
    {
        cin >> h[i];
        if (i>1)
        {
            B.Add(min(h[i],h[i-1]),1);
            B.Add(max(h[i],h[i-1])+1,-1);
        }
    }
    while (m--)
    {
        cin >> t >> x;
        if (t==2)
        {
            cout << B.Calc(x) << "\n";
            continue;
        }
        cin >> y;
        if (x>1)
        {
            B.Add(min(h[x],h[x-1]),-1);
            B.Add(max(h[x],h[x-1])+1,1);
        }
        if (x<n)
        {
            B.Add(min(h[x],h[x+1]),-1);
            B.Add(max(h[x],h[x+1])+1,1);
        }
        h[x]=y;
        if (x>1)
        {
            B.Add(min(h[x],h[x-1]),1);
            B.Add(max(h[x],h[x-1])+1,-1);
        }
        if (x<n)
        {
            B.Add(min(h[x],h[x+1]),1);
            B.Add(max(h[x],h[x+1])+1,-1);
        }
    }
    return 0;
}

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