제출 #598182

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
598182		daisy2	Simple game (IZhO17_game)	C++14	100 / 100	77 ms	11144 KiB

game

#include<bits/stdc++.h>
#include<vector>
#define endl '\n'
using namespace std;
long long n,h[100005],fenwick[1000005],m,t,num,p;
void upd(long long x,long long val)
{
    for(int i=x;i<=1000000;i += i& -i)
    {
        fenwick[i]+=val;
    }
}
void update(long long a,long long b,long long v)
{
    if(a>b) swap(a,b);
    upd(a,v);
    upd(b,-v);
}
long long query(long long x)
{
    long long r=0;
    for(long long i=x;i>0; i-= i & -i)
    {
        r+=fenwick[i];
    }
    return r;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;

    cin>>h[1];
    for(int i=2;i<=n;i++)
    {
        cin>>h[i];
        update(h[i-1],h[i],1);
    }
    for(int i=1;i<=m;i++)
    {
        cin>>t>>num;
        if(t==1)
        {
            cin>>p;
            if(num>1){
                update(h[num-1],h[num],-1);
                update(h[num-1],p,1);
            }

            if(num<n){
                update(h[num],h[num+1],-1);
                update(p,h[num+1],1);
            }
            h[num]=p;
            continue;
        }
        cout<<query(num)<<endl;
    }

}

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