oj.uz

Submission #290307

# Submission time Handle Problem Language Result Execution time Memory
290307 2020-09-03T15:42:23 Z MasterTaster Simple game (IZhO17_game) C++14
0 / 100
 3 ms 3968 KB 
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int, int>
#define xx first
#define yy second
#define endl "\n"
#define MAXN 1000007

int n, m, arr[100010], bit[1000010];

void upd(int x, int v)
{
    while(x<MAXN)
    {
        bit[x]+=v;
        x+=x&(-x);
    }
}
int sum(int x)
{
    int suma=0;
    while (x)
    {
        suma+=bit[x];
        x-=x&(-x);
    }
    return suma;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin>>n>>m;

    for (int i=0; i<n; i++) cin>>arr[i];

    for (int i=1; i<n; i++)
    {
        upd(min(arr[i], arr[i-1]), 1);
        upd(max(arr[i], arr[i-1])+1, -1);
    }

    while (m--)
    {
        int q; cin>>q;
        if (q==1)
        {
            int i, x; cin>>i>>x;
            i--;
            if (i!=0)
            {
                upd(min(arr[i], arr[i-1]), -1);
                upd(max(arr[i], arr[i-1])+1, 1);

                upd(min(x, arr[i-1]), -1);
                upd(max(x, arr[i-1])+1, 1);
            }
            if (i!=n-1)
            {
                upd(min(arr[i], arr[i+1]), -1);
                upd(max(arr[i], arr[i+1])+1, 1);

                upd(min(x, arr[i+1]), -1);
                upd(max(x, arr[i+1])+1, 1);
            }
            arr[i]=x;
        }
        else
        {
            int h; cin>>h;
            cout<<sum(h)<<endl;
        }
    }
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 3 ms 3968 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 384 KB Output is correct
2 Incorrect 3 ms 3968 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 384 KB Output is correct
2 Incorrect 3 ms 3968 KB Output isn't correct
3 Halted 0 ms 0 KB -