oj.uz

Submission #624104

# Submission time Handle Problem Language Result Execution time Memory
624104 2022-08-07T09:09:39 Z Hanksburger Simple game (IZhO17_game) C++17
100 / 100
 57 ms 6844 KB 
#include <bits/stdc++.h>
using namespace std;
int bit[1000005], a[100005];
void update(int x, int y)
{
    for (int i=x; i<=1e6; i+=i&(-i))
        bit[i]+=y;
}
int query(int x)
{
    int ans=0;
    for (int i=x; i; i-=i&(-i))
        ans+=bit[i];
    return ans;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i=1; i<=n; i++)
    {
        cin >> a[i];
        if (i>=2)
        {
            update(min(a[i-1], a[i]), 1);
            update(max(a[i-1], a[i]), -1);
        }
    }
    for (int i=1; i<=m; i++)
    {
        int t, x, y;
        cin >> t >> x;
        if (t==1)
        {
            cin >> y;
            if (x>=2)
            {
                update(min(a[x-1], a[x]), -1);
                update(max(a[x-1], a[x]), 1);
            }
            if (x<n)
            {
                update(min(a[x], a[x+1]), -1);
                update(max(a[x], a[x+1]), 1);
            }
            a[x]=y;
            if (x>=2)
            {
                update(min(a[x-1], a[x]), 1);
                update(max(a[x-1], a[x]), -1);
            }
            if (x<n)
            {
                update(min(a[x], a[x+1]), 1);
                update(max(a[x], a[x+1]), -1);
            }
        }
        else
            cout << query(x) << '\n';
    }
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 4052 KB Output is correct
3 Correct 2 ms 4052 KB Output is correct
4 Correct 2 ms 4052 KB Output is correct
5 Correct 3 ms 4052 KB Output is correct
6 Correct 2 ms 4160 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 4052 KB Output is correct
3 Correct 2 ms 4052 KB Output is correct
4 Correct 2 ms 4052 KB Output is correct
5 Correct 3 ms 4052 KB Output is correct
6 Correct 2 ms 4160 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 30 ms 1640 KB Output is correct
9 Correct 38 ms 6748 KB Output is correct
10 Correct 37 ms 6796 KB Output is correct
11 Correct 29 ms 1576 KB Output is correct
12 Correct 35 ms 2788 KB Output is correct
13 Correct 35 ms 2908 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 4052 KB Output is correct
3 Correct 2 ms 4052 KB Output is correct
4 Correct 2 ms 4052 KB Output is correct
5 Correct 3 ms 4052 KB Output is correct
6 Correct 2 ms 4160 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 30 ms 1640 KB Output is correct
9 Correct 38 ms 6748 KB Output is correct
10 Correct 37 ms 6796 KB Output is correct
11 Correct 29 ms 1576 KB Output is correct
12 Correct 35 ms 2788 KB Output is correct
13 Correct 35 ms 2908 KB Output is correct
14 Correct 50 ms 6732 KB Output is correct
15 Correct 57 ms 6832 KB Output is correct
16 Correct 53 ms 6732 KB Output is correct
17 Correct 50 ms 6736 KB Output is correct
18 Correct 47 ms 6844 KB Output is correct