oj.uz

Submission #345699

# Submission time Handle Problem Language Result Execution time Memory
345699 2021-01-07T22:39:14 Z mat_v Simple game (IZhO17_game) C++14
100 / 100
 102 ms 9848 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<int,int>


using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
    int n,q;

int bit1[1000005];
int bit2[1000005];

void apd1(int x, int val){
    while(x > 0){
        bit1[x] += val;
        x -= (x&-x);
    }
}
int kv1(int x){
    int ans = 0;
    while(x <= 1000000){
        ans += bit1[x];
        x += (x&-x);
    }
    return ans;
}
void apd2(int x, int val){
    while(x > 0){
        bit2[x] += val;
        x -= (x&-x);
    }
}
int kv2(int x){
    int ans = 0;
    while(x <= 1000000){
        ans += bit2[x];
        x += (x&-x);
    }
    return ans;
}
int niz[1000005];

void izbaci(int pos){
    if(pos > 1 && niz[pos] != niz[pos - 1]){
        apd1(min(niz[pos], niz[pos - 1]), -1);
        apd2(max(niz[pos], niz[pos - 1]), -1);

    }
    if(pos < n && niz[pos] != niz[pos + 1]){

        apd1(min(niz[pos], niz[pos + 1]), -1);
        apd2(max(niz[pos], niz[pos + 1]), -1);
    }
}
void ubaci(int pos, int val){
    niz[pos] = val;
    if(pos > 1 && niz[pos] != niz[pos - 1]){
        apd1(min(niz[pos], niz[pos - 1]), 1);
        apd2(max(niz[pos], niz[pos - 1]), 1);

    }
    if(pos < n && niz[pos] != niz[pos + 1]){

        apd1(min(niz[pos], niz[pos + 1]), 1);
        apd2(max(niz[pos], niz[pos + 1]), 1);
    }
}

int main()
{

    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> n >> q;
    ff(i,1,n){
        cin >> niz[i];
    }
    ff(i,1,n - 1){
        if(niz[i] == niz[i + 1])continue;
        apd1(min(niz[i],niz[i + 1]), 1);
        apd2(max(niz[i],niz[i + 1]), 1);
    }
    while(q--){
        int idx;
        cin >> idx;
        if(idx == 2){
            int h;
            cin >> h;
            //cout << kv2(h) << " " << kv1(h) << "\n";
            cout << kv2(h) - kv1(h) << "\n";
        }
        else{
            int pos,val;
            cin >> pos >> val;
            izbaci(pos);
            ubaci(pos, val);
        }
    }
    return 0;
}

Compilation message

game.cpp: In function 'int main()':
game.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
game.cpp:88:5: note: in expansion of macro 'ff'
   88 |     ff(i,1,n){
      |     ^~
game.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
game.cpp:91:5: note: in expansion of macro 'ff'
   91 |     ff(i,1,n - 1){
      |     ^~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 6 ms 7108 KB Output is correct
3 Correct 6 ms 6932 KB Output is correct
4 Correct 7 ms 7168 KB Output is correct
5 Correct 6 ms 7020 KB Output is correct
6 Correct 5 ms 7040 KB Output is correct
7 Correct 2 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 6 ms 7108 KB Output is correct
3 Correct 6 ms 6932 KB Output is correct
4 Correct 7 ms 7168 KB Output is correct
5 Correct 6 ms 7020 KB Output is correct
6 Correct 5 ms 7040 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 39 ms 1664 KB Output is correct
9 Correct 88 ms 9848 KB Output is correct
10 Correct 76 ms 9836 KB Output is correct
11 Correct 35 ms 1644 KB Output is correct
12 Correct 46 ms 2284 KB Output is correct
13 Correct 48 ms 2156 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 6 ms 7108 KB Output is correct
3 Correct 6 ms 6932 KB Output is correct
4 Correct 7 ms 7168 KB Output is correct
5 Correct 6 ms 7020 KB Output is correct
6 Correct 5 ms 7040 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 39 ms 1664 KB Output is correct
9 Correct 88 ms 9848 KB Output is correct
10 Correct 76 ms 9836 KB Output is correct
11 Correct 35 ms 1644 KB Output is correct
12 Correct 46 ms 2284 KB Output is correct
13 Correct 48 ms 2156 KB Output is correct
14 Correct 96 ms 9496 KB Output is correct
15 Correct 85 ms 9452 KB Output is correct
16 Correct 102 ms 9508 KB Output is correct
17 Correct 89 ms 9380 KB Output is correct
18 Correct 85 ms 9528 KB Output is correct