Submission #878368

#	Time	Username	Problem	Language	Result	Execution time	Memory
878368		alexdd	Simple game (IZhO17_game)	C++17	100 / 100	52 ms	6952 KiB

game

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[100005];
int aib[1000005];
int qry(int poz)
{
    int aux=0;
    for(int i=poz;i>0;i-=(i&(-i)))
        aux+=aib[i];
    return aux;
}
void upd(int poz, int newv)
{
    for(int i=poz;i<=1000005;i+=(i&(-i)))
        aib[i]+=newv;
}
void adauga(int prec, int cur, int semn)
{
    if(prec>cur)
        swap(prec,cur);
    upd(prec,semn);
    upd(cur+1,-semn);
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(i>1)
            adauga(a[i-1],a[i],1);
    }
    int tip,x,y;
    for(int i=0;i<m;i++)
    {
        cin>>tip;
        if(tip==1)
        {
            cin>>x>>y;
            if(x>1) adauga(a[x-1],a[x],-1);
            if(x<n) adauga(a[x],a[x+1],-1);
            a[x]=y;
            if(x>1) adauga(a[x-1],a[x],1);
            if(x<n) adauga(a[x],a[x+1],1);
        }
        else
        {
            cin>>x;
            cout<<qry(x)<<"\n";
        }
    }
    return 0;
}
/**

a[i-1] <= h <= a[i]

a[i-1] >= h >= a[i]

3 3
1 5 1
2 3
1 1 5
2 3

*/

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