Submission #1188781

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188781		prideliqueee	Simple game (IZhO17_game)	C++20	100 / 100	208 ms	21720 KiB

game

#include<bits/stdc++.h>
using namespace std;
int lz[4000010];
int cnt[4000010];
int og[1000010];
void pushlz(int l,int r,int i)
{
    cnt[i]+=lz[i];
    if(l!=r)
    {
        lz[i*2]+=lz[i];
        lz[i*2+1]+=lz[i];
    }
    lz[i]=0;
}
void update(int l,int r,int i,int ql,int qr,int val)
{
    pushlz(l,r,i);
    if(qr<l||ql>r)
    return;
    if(ql<=l&&qr>=r)
    {
        lz[i]+=val;
        pushlz(l,r,i);
        return;
    }
    int mid=(l+r)/2;
    update(l,mid,i*2,ql,qr,val);
    update(mid+1,r,i*2+1,ql,qr,val);
}
int ans;
void query(int l,int r,int i,int index)
{
    pushlz(l,r,i);
    if(index<l||index>r)
    return;
    if(l==r)
    {
        ans=cnt[i];
        return;
    }
    int mid=(l+r)/2;
    query(l,mid,i*2,index);
    query(mid+1,r,i*2+1,index);
}
int main()
{
    int n,m;
    cin>>n>>m;
    int a[n+1];
    for(int i=1;i<=n;i++)
    cin>>a[i];
    for(int i=2;i<=n;i++)
    {
        int a1=a[i-1],a2=a[i];
        if(a1>a2)
        swap(a1,a2);
        og[a1]++;
        og[a2+1]--;
    }
    for(int i=1;i<=1000000;i++)
    og[i]+=og[i-1];
    //build(1,1000001,1);
    for(int i=0;i<m;i++)
    {
        int x;
        cin>>x;
        if(x==1)
        {
            int index,e;
            cin>>index>>e;
            if(index!=1)
            {
                int a1=a[index];
                int a2=a[index-1];
                if(a1>a2)
                swap(a1,a2);
                update(1,1000000,1,a1,a2,-1);
                a1=a[index-1];
                a2=e;
                if(a1>a2)
                swap(a1,a2);
                update(1,1000000,1,a1,a2,1);
            }
            if(index!=n)
            {
                int a1=a[index];
                int a2=a[index+1];
                if(a1>a2)
                swap(a1,a2);
                //cout<<a1<<" "<<a2<<"-1"<<endl;
                update(1,1000000,1,a1,a2,-1);
                a1=a[index+1];
                a2=e;
                if(a1>a2)
                swap(a1,a2);
                //cout<<a1<<" "<<a2<<"1"<<endl;
                update(1,1000000,1,a1,a2,1);
            }
            a[index]=e;
        }
        else
        {
            int h;
            cin>>h;
            query(1,1000000,1,h);
            cout<<ans+og[h]<<'\n';
            /*for(int j=1;j<=5;j++)
            {
                query(1,10000,1,j);
                cout<<ans<<endl;
            }*/
        }
    }
}

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