oj.uz

Submission #878367

# Submission time Handle Problem Language Result Execution time Memory
878367 2023-11-24T08:56:49 Z alexdd Simple game (IZhO17_game) C++17
0 / 100
 1 ms 4700 KB 
#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);
        }
        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
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4556 KB Output is correct
2 Incorrect 1 ms 4700 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4556 KB Output is correct
2 Incorrect 1 ms 4700 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4556 KB Output is correct
2 Incorrect 1 ms 4700 KB Output isn't correct
3 Halted 0 ms 0 KB -