oj.uz

Submission #878371

# Submission time Handle Problem Language Result Execution time Memory
878371 2023-11-24T08:58:43 Z heeheeheehaaw Simple game (IZhO17_game) C++17
100 / 100
 42 ms 8796 KB 
#include <bits/stdc++.h>

using namespace std;

int aib[1000005];
int v[1000005];
int n, q;

void update(int poz, int val)
{
    for(int i = poz; i <= 1000000; i += (i & (-i)))
        aib[i] += val;
    return;
}

int query(int poz)
{
    int sum = 0;
    for(int i = poz; i >= 1; i -= (i & (-i)))
        sum += aib[i];
    return sum;
}

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

    cin>>n>>q;
    for(int i = 1; i <= n; i++)
        cin>>v[i];
    for(int i = 2; i <= n; i++)
    {
        int sus = max(v[i], v[i - 1]);
        int jos = min(v[i], v[i - 1]);
        update(jos, 1);
        update(sus, -1);
    }

    for(int i = 1; i <= q; i++)
    {
        int tip;
        cin>>tip;
        if(tip == 1)
        {
            int a, b;
            cin>>a>>b;
            if(a > 1)
            {
                int st = a - 1;
                int sus = max(v[st], v[a]), jos = min(v[st], v[a]);
                update(sus, 1);
                update(jos, -1);
                sus = max(v[st], b);
                jos = min(v[st], b);
                update(sus, -1);
                update(jos, 1);
            }
            if(a < n)
            {
                int st = a + 1;
                int sus = max(v[st], v[a]), jos = min(v[st], v[a]);
                update(sus, 1);
                update(jos, -1);
                sus = max(v[st], b);
                jos = min(v[st], b);
                update(sus, -1);
                update(jos, 1);
            }

            v[a] = b;
        }
        else
        {
            int a;
            cin>>a;
            cout<<query(a)<<'\n';
        }
    }
    return 0;
}

/*

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

*/

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 2 ms 5724 KB Output is correct
4 Correct 1 ms 5724 KB Output is correct
5 Correct 2 ms 5724 KB Output is correct
6 Correct 2 ms 5724 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 2 ms 5724 KB Output is correct
4 Correct 1 ms 5724 KB Output is correct
5 Correct 2 ms 5724 KB Output is correct
6 Correct 2 ms 5724 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 28 ms 6868 KB Output is correct
9 Correct 30 ms 8788 KB Output is correct
10 Correct 29 ms 8796 KB Output is correct
11 Correct 28 ms 7000 KB Output is correct
12 Correct 27 ms 7260 KB Output is correct
13 Correct 29 ms 7356 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 2 ms 5724 KB Output is correct
4 Correct 1 ms 5724 KB Output is correct
5 Correct 2 ms 5724 KB Output is correct
6 Correct 2 ms 5724 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 28 ms 6868 KB Output is correct
9 Correct 30 ms 8788 KB Output is correct
10 Correct 29 ms 8796 KB Output is correct
11 Correct 28 ms 7000 KB Output is correct
12 Correct 27 ms 7260 KB Output is correct
13 Correct 29 ms 7356 KB Output is correct
14 Correct 38 ms 8540 KB Output is correct
15 Correct 42 ms 8572 KB Output is correct
16 Correct 38 ms 8540 KB Output is correct
17 Correct 38 ms 8512 KB Output is correct
18 Correct 39 ms 8540 KB Output is correct