oj.uz

Submission #340213

# Submission time Handle Problem Language Result Execution time Memory
340213 2020-12-27T09:56:05 Z Sprdalo Simple game (IZhO17_game) C++17
100 / 100
 151 ms 36224 KB 
#include <bits/stdc++.h>

using namespace std;

#define int ll
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pi> vp;
typedef vector<pl> vpl;

template<int MAXN>
struct segtr{
    //To change the purpose of the segtree just redefine the operators
    struct node{
        int x;
        node(int x = 0) : x(x) {}
        node& operator+= (const node& other){
            x += other.x;
            return *this;
        }
        node operator+ (const node& other){
            node tmp = *this;
            return tmp += other;
        }
    };
    
    node a[2*MAXN];
    
    //Initialize the array
    void init(){
        for(int i = 1; i <= MAXN; ++i){
            a[i+MAXN-1] = node{};
        }
        for(int i = MAXN-1; i > 0; --i){
            a[i] = a[2*i] + a[2*i+1];
        }
    }
    
    //Sets the node and updates the tree
    void set(int pos, node val){
        pos += MAXN-1;
        a[pos] = val;
        
        while(pos > 1){
            pos /= 2;
            a[pos] = a[2*pos] + a[2*pos+1];
        }
    }
    inline void add(int pos, node val){ //Just forwards to set
        set(pos, node{a[pos+MAXN-1]+val});
    }
    
    //Gets the range query
    node get(int l, int r, int pos = 1, int rl = 1, int rr = MAXN){
        if(r < rl || rr < l){ return node{}; }
        if(l <= rl && rr <= r){ return a[pos]; }
        
        int rm = (rl+rr)/2;
        return get(l, r, 2*pos, rl, rm) + get(l, r, 2*pos+1, rm+1, rr);
    }
    
};
segtr<131072*16> drvo;

void oduzmi(int a, int b){
    //cout << "BRISI " << a << ' ' << b << endl;
    if (a > b)
        swap(a, b);
    drvo.add(a, -1);
    drvo.add(b+1, 1);
}

void dodaj(int a, int b){
    //cout << "DODAJ " << a << ' ' << b << endl;
    if (a > b)
        swap(a, b);
    drvo.add(a,1);
    drvo.add(b+1,-1);
}

signed main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); 
    cout.tie(nullptr); 
    cerr.tie(nullptr); 
    drvo.init();

    int n, m;
    cin >> n >> m;

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

    for (int i = 2; i <= n; ++i){
        dodaj(a[i-1],a[i]);
    }

    for (int e = 0; e < m; ++e){
        int z;
        cin >> z;

        if (z == 2){
            int h;
            cin >> h;
            cout << drvo.get(1, h).x << '\n';
            continue;
        }

        int pos, val;
        cin >> pos >> val;

        if (pos > 1) oduzmi(a[pos], a[pos-1]);
        if (pos < n) oduzmi(a[pos], a[pos+1]);
        a[pos] = val;
        if (pos > 1) dodaj(a[pos], a[pos-1]);
        if (pos < n) dodaj(a[pos], a[pos+1]);
    }
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 33132 KB Output is correct
2 Correct 26 ms 33132 KB Output is correct
3 Correct 26 ms 33152 KB Output is correct
4 Correct 26 ms 33132 KB Output is correct
5 Correct 27 ms 33132 KB Output is correct
6 Correct 26 ms 33132 KB Output is correct
7 Correct 26 ms 33132 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 33132 KB Output is correct
2 Correct 26 ms 33132 KB Output is correct
3 Correct 26 ms 33152 KB Output is correct
4 Correct 26 ms 33132 KB Output is correct
5 Correct 27 ms 33132 KB Output is correct
6 Correct 26 ms 33132 KB Output is correct
7 Correct 26 ms 33132 KB Output is correct
8 Correct 94 ms 34540 KB Output is correct
9 Correct 115 ms 36204 KB Output is correct
10 Correct 116 ms 36224 KB Output is correct
11 Correct 100 ms 34924 KB Output is correct
12 Correct 86 ms 35948 KB Output is correct
13 Correct 111 ms 36096 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 33132 KB Output is correct
2 Correct 26 ms 33132 KB Output is correct
3 Correct 26 ms 33152 KB Output is correct
4 Correct 26 ms 33132 KB Output is correct
5 Correct 27 ms 33132 KB Output is correct
6 Correct 26 ms 33132 KB Output is correct
7 Correct 26 ms 33132 KB Output is correct
8 Correct 94 ms 34540 KB Output is correct
9 Correct 115 ms 36204 KB Output is correct
10 Correct 116 ms 36224 KB Output is correct
11 Correct 100 ms 34924 KB Output is correct
12 Correct 86 ms 35948 KB Output is correct
13 Correct 111 ms 36096 KB Output is correct
14 Correct 148 ms 36204 KB Output is correct
15 Correct 145 ms 36204 KB Output is correct
16 Correct 148 ms 36204 KB Output is correct
17 Correct 149 ms 36204 KB Output is correct
18 Correct 151 ms 36204 KB Output is correct