oj.uz

Submission #313801

# Submission time Handle Problem Language Result Execution time Memory
313801 2020-10-17T06:03:55 Z Trickster Simple game (IZhO17_game) C++14
100 / 100
 675 ms 19576 KB 
#include <algorithm>
#include <string.h>
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
#include <map>

using namespace std;

#define N 1000010
#define ff first
#define ss second
#define ll long long
#define pb push_back
#define mod 1000000007
#define pii pair <int, int>
#define sz(a) int(a.size())
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
ll bigmod(ll a,ll e) {if(e==0)return 1;ll x=bigmod(a*a%mod,e>>1);return e&1?x*a%mod:x;}

int n, q;
int v[N];
int T[N*4];
int L[N*4];

void shift(int node, int to, int l, int r)
{
    L[to] += L[node];
    T[to] += L[node] * (r-l+1);
}

void upd(int a, int b, int x, int l, int r, int node)
{
    if(l > b || r < a) return;

    if(l >= a && r <= b) {
        T[node] += (r-l+1) * x;
        L[node] += x;
        return;
    }

    shift(node, node*2, l, (l+r)/2);
    shift(node, node*2+1, (l+r)/2+1, r);
    L[node] = 0;

    upd(a, b, x, l, (l+r)/2, node*2);
    upd(a, b, x, (l+r)/2+1, r, node*2+1);

    T[node] = T[node*2] + T[node*2+1];
}

int tap(int pos, int l, int r, int node)
{
    if(l == r) return T[node];

    shift(node, node*2, l, (l+r)/2);
    shift(node, node*2+1, (l+r)/2+1, r);
    L[node] = 0;

    if(pos <= (l+r)/2) return tap(pos, l, (l+r)/2, node*2);
    else return tap(pos, (l+r)/2+1, r, node*2+1);
}

int main()
{
    cin >> n >> q;

    for(int i = 1; i <= n; i++) cin >> v[i];

    for(int i = 1; i < n; i++) upd(min(v[i], v[i+1]), max(v[i+1], v[i]), 1, 1, 1000000, 1);

    while(q--) {
        int tp, pos, x;
        cin >> tp >> pos;

        if(tp == 1) {
            cin >> x;

            if(pos != 1) {
                int a = v[pos], b = v[pos-1];

                upd(min(a, b), max(a, b), -1, 1, 1000000, 1);
                upd(min(x, b), max(x, b), 1, 1, 1000000, 1);
            }
            if(pos != n) {
                int a = v[pos], b = v[pos+1];

                upd(min(a, b), max(a, b), -1, 1, 1000000, 1);
                upd(min(x, b), max(x, b), 1, 1, 1000000, 1);
            }
            v[pos] = x;
        }
        else cout << tap(pos, 1, 1000000, 1) << "\n";
    }
}
/*
3 3
1 5 1
2 3
1 1 5
2 3
*/

Compilation message

game.cpp:22: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
   22 | #pragma GCC optimization ("O3")
      | 
game.cpp:23: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
   23 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 15 ms 14848 KB Output is correct
3 Correct 15 ms 14464 KB Output is correct
4 Correct 15 ms 14720 KB Output is correct
5 Correct 15 ms 14848 KB Output is correct
6 Correct 15 ms 14720 KB Output is correct
7 Correct 11 ms 12808 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 15 ms 14848 KB Output is correct
3 Correct 15 ms 14464 KB Output is correct
4 Correct 15 ms 14720 KB Output is correct
5 Correct 15 ms 14848 KB Output is correct
6 Correct 15 ms 14720 KB Output is correct
7 Correct 11 ms 12808 KB Output is correct
8 Correct 362 ms 1900 KB Output is correct
9 Correct 546 ms 19324 KB Output is correct
10 Correct 547 ms 19576 KB Output is correct
11 Correct 353 ms 1740 KB Output is correct
12 Correct 448 ms 3320 KB Output is correct
13 Correct 432 ms 19388 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 15 ms 14848 KB Output is correct
3 Correct 15 ms 14464 KB Output is correct
4 Correct 15 ms 14720 KB Output is correct
5 Correct 15 ms 14848 KB Output is correct
6 Correct 15 ms 14720 KB Output is correct
7 Correct 11 ms 12808 KB Output is correct
8 Correct 362 ms 1900 KB Output is correct
9 Correct 546 ms 19324 KB Output is correct
10 Correct 547 ms 19576 KB Output is correct
11 Correct 353 ms 1740 KB Output is correct
12 Correct 448 ms 3320 KB Output is correct
13 Correct 432 ms 19388 KB Output is correct
14 Correct 673 ms 19576 KB Output is correct
15 Correct 675 ms 19320 KB Output is correct
16 Correct 666 ms 19448 KB Output is correct
17 Correct 671 ms 19576 KB Output is correct
18 Correct 671 ms 19416 KB Output is correct