oj.uz

Submission #553258

# Submission time Handle Problem Language Result Execution time Memory
553258 2022-04-25T08:57:15 Z Jarif_Rahman Game (IOI13_game) C++17
100 / 100
 4564 ms 61760 KB 
#include "game.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

const int lim1 = 22000*35, lim2 = 22000*35;

struct Node{
    Node *l = nullptr, *r = nullptr;
    int X, Y;
    ll x, s;
    Node(){}
    Node(int _X, int _Y, ll _x){
        X = _X, Y = _Y, x = _x, s = x;
    }
};

Node T1[lim1];
int cnt1 = 0;

Node* newNode(int X, int Y, ll x){
    T1[cnt1] = Node(X, Y, x);
    return &T1[cnt1++];
}

namespace Treap{
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    void upd_nd(Node *nd){
        if(!nd) return;
        nd->s = nd->x;
        if(nd->l) nd->s = __gcd(nd->s, nd->l->s);
        if(nd->r) nd->s = __gcd(nd->s, nd->r->s);
    }

    pair<Node*, Node*> split(Node* root, int X){
        if(!root) return {nullptr, nullptr};
        if(root->X <= X){
            auto [L, R] = split(root->r, X);
            root->r = L;
            upd_nd(root);
            return {root, R};
        }
        else{
            auto [L, R] = split(root->l, X);
            root->l = R;
            upd_nd(root);
            return {L, root};
        }
    }

    Node* merge(Node* l, Node* r){
        if(!l) return r;
        if(!r) return l;
        if(l->Y >= r->Y){
            l->r = merge(l->r, r);
            upd_nd(l);
            return l;
        }
        else{
            r->l = merge(l, r->l);
            upd_nd(r);
            return r;
        }
    }

    bool search_upd(Node *nd, int X, ll x){
        if(!nd) return 0;
        if(nd->X == X){
            nd->x = x;
            upd_nd(nd);
            return 1;
        }
        if(nd->X > X){
            if(search_upd(nd->l, X, x)){
                upd_nd(nd);
                return 1;
            }
            return 0;
        }
        else{
            if(search_upd(nd->r, X, x)){
                upd_nd(nd);
                return 1;
            }
            return 0;
        }
    }

    void insert(Node *&rt, int X, ll x){
        auto [L, R] = split(rt, X);
        Node* nd = newNode(X, uniform_int_distribution(INT_MIN, INT_MAX)(rng), x);
        auto _rt = merge(L, nd);
        _rt = merge(_rt, R);
        rt = _rt;
    }

    void update(Node *&root, int X, ll x){
        if(!search_upd(root, X, x)) insert(root, X, x);
    }

    ll get(Node* nd, int X){
        if(!nd) return 0;
        if(nd->X == X) return nd->x;
        if(nd->X > X) return get(nd->l, X);
        return get(nd->r, X);
    }

    ll get(Node *& rt, int a, int b){
        auto [A, D] = split(rt, a-1);
        auto [B, C] = split(D, b);
        ll ret = B?B->s:0;
        auto _rt = merge(A, B);
        _rt = merge(_rt, C);
        rt = _rt;
        return ret;
    }
};

struct Node2d{
    Node2d *l = nullptr, *r = nullptr;
    Node* tp = nullptr;
    Node2d(){}
};

Node2d T2[lim2];
int cnt2 = 0;

Node2d* newNode2d(){
    return &T2[cnt2++];
}

struct sparse_segtree2d{
    int n, m;
    Node2d* root;
    sparse_segtree2d(int _n, int _m){
        n = _n, m = _m;
        root = newNode2d();
    }

    void upd(Node2d *nd, int l, int r, int a, int b, ll x){
        if(l != r){
            if(a <= (l+r)/2){
                if(!nd->l) nd->l = newNode2d();
                upd(nd->l, l, (l+r)/2, a, b, x);
            }
            else{
                if(!nd->r) nd->r = newNode2d();
                upd(nd->r, (l+r)/2+1, r, a, b, x);
            }
            ll s = 0;
            if(nd->l) s = __gcd(s, Treap::get(nd->l->tp, b));
            if(nd->r) s = __gcd(s, Treap::get(nd->r->tp, b));
            Treap::update(nd->tp, b, s);
        }
        else Treap::update(nd->tp, b, x);
    }
    void upd(int a, int b, ll x){
        upd(root, 0, n-1, a, b, x);
    }

    ll get(Node2d* nd, int L, int R, int a1, int b1, int a2, int b2){
        if(L > a2 || R < a1) return 0;
        if(L >= a1 && R <= a2) return Treap::get(nd->tp, b1, b2);
        int md = (L+R)/2;
        ll rt = 0;
        if(nd->l) rt = __gcd(rt, get(nd->l, L, md, a1, b1, a2, b2));
        if(nd->r) rt = __gcd(rt, get(nd->r, md+1, R, a1, b1, a2, b2));
        return rt;
    }
    ll get(int a1, int b1, int a2, int b2){
        return get(root, 0, n-1, a1, b1, a2, b2);
    }
};

sparse_segtree2d sp(0, 0);

void init(int R, int C){
    sp = sparse_segtree2d(R, C);
}

void update(int P, int Q, ll K){
    sp.upd(P, Q, K);
}

ll calculate(int P, int Q, int U, int V){
    return sp.get(P, Q, U, V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 48468 KB Output is correct
2 Correct 20 ms 48424 KB Output is correct
3 Correct 20 ms 48460 KB Output is correct
4 Correct 20 ms 48468 KB Output is correct
5 Correct 18 ms 48400 KB Output is correct
6 Correct 19 ms 48456 KB Output is correct
7 Correct 18 ms 48448 KB Output is correct
8 Correct 17 ms 48468 KB Output is correct
9 Correct 20 ms 48468 KB Output is correct
10 Correct 20 ms 48444 KB Output is correct
11 Correct 19 ms 48400 KB Output is correct
12 Correct 19 ms 48464 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 48416 KB Output is correct
2 Correct 21 ms 48516 KB Output is correct
3 Correct 20 ms 48512 KB Output is correct
4 Correct 867 ms 52660 KB Output is correct
5 Correct 390 ms 52808 KB Output is correct
6 Correct 1154 ms 49636 KB Output is correct
7 Correct 1392 ms 49228 KB Output is correct
8 Correct 898 ms 50072 KB Output is correct
9 Correct 1265 ms 49296 KB Output is correct
10 Correct 1114 ms 48968 KB Output is correct
11 Correct 21 ms 48460 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 48496 KB Output is correct
2 Correct 22 ms 48528 KB Output is correct
3 Correct 21 ms 48444 KB Output is correct
4 Correct 23 ms 48508 KB Output is correct
5 Correct 21 ms 48488 KB Output is correct
6 Correct 19 ms 48468 KB Output is correct
7 Correct 21 ms 48468 KB Output is correct
8 Correct 19 ms 48484 KB Output is correct
9 Correct 20 ms 48412 KB Output is correct
10 Correct 19 ms 48476 KB Output is correct
11 Correct 21 ms 48440 KB Output is correct
12 Correct 1206 ms 52684 KB Output is correct
13 Correct 2603 ms 49220 KB Output is correct
14 Correct 344 ms 49048 KB Output is correct
15 Correct 2875 ms 49352 KB Output is correct
16 Correct 271 ms 49248 KB Output is correct
17 Correct 1843 ms 49840 KB Output is correct
18 Correct 2957 ms 49532 KB Output is correct
19 Correct 2579 ms 49780 KB Output is correct
20 Correct 2505 ms 49240 KB Output is correct
21 Correct 19 ms 48468 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 48420 KB Output is correct
2 Correct 19 ms 48400 KB Output is correct
3 Correct 19 ms 48428 KB Output is correct
4 Correct 19 ms 48468 KB Output is correct
5 Correct 21 ms 48416 KB Output is correct
6 Correct 23 ms 48468 KB Output is correct
7 Correct 23 ms 48472 KB Output is correct
8 Correct 20 ms 48476 KB Output is correct
9 Correct 20 ms 48468 KB Output is correct
10 Correct 20 ms 48468 KB Output is correct
11 Correct 19 ms 48468 KB Output is correct
12 Correct 862 ms 52524 KB Output is correct
13 Correct 371 ms 52796 KB Output is correct
14 Correct 1140 ms 49564 KB Output is correct
15 Correct 1334 ms 49272 KB Output is correct
16 Correct 886 ms 50216 KB Output is correct
17 Correct 1414 ms 49400 KB Output is correct
18 Correct 1266 ms 49028 KB Output is correct
19 Correct 1268 ms 52500 KB Output is correct
20 Correct 2921 ms 49332 KB Output is correct
21 Correct 362 ms 49012 KB Output is correct
22 Correct 2879 ms 49236 KB Output is correct
23 Correct 278 ms 49260 KB Output is correct
24 Correct 1734 ms 49932 KB Output is correct
25 Correct 3001 ms 49740 KB Output is correct
26 Correct 2484 ms 49864 KB Output is correct
27 Correct 2560 ms 49104 KB Output is correct
28 Correct 950 ms 49268 KB Output is correct
29 Correct 1693 ms 52088 KB Output is correct
30 Correct 3327 ms 49056 KB Output is correct
31 Correct 2996 ms 49468 KB Output is correct
32 Correct 416 ms 48972 KB Output is correct
33 Correct 716 ms 49040 KB Output is correct
34 Correct 472 ms 49144 KB Output is correct
35 Correct 2004 ms 49924 KB Output is correct
36 Correct 3836 ms 49608 KB Output is correct
37 Correct 3147 ms 49896 KB Output is correct
38 Correct 3196 ms 49420 KB Output is correct
39 Correct 2577 ms 49780 KB Output is correct
40 Correct 19 ms 48464 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 48384 KB Output is correct
2 Correct 22 ms 48460 KB Output is correct
3 Correct 22 ms 48496 KB Output is correct
4 Correct 25 ms 48416 KB Output is correct
5 Correct 21 ms 48396 KB Output is correct
6 Correct 20 ms 48468 KB Output is correct
7 Correct 20 ms 48400 KB Output is correct
8 Correct 20 ms 48560 KB Output is correct
9 Correct 20 ms 48484 KB Output is correct
10 Correct 20 ms 48460 KB Output is correct
11 Correct 20 ms 48444 KB Output is correct
12 Correct 868 ms 52804 KB Output is correct
13 Correct 382 ms 52872 KB Output is correct
14 Correct 1154 ms 49492 KB Output is correct
15 Correct 1305 ms 49456 KB Output is correct
16 Correct 885 ms 50184 KB Output is correct
17 Correct 1297 ms 49516 KB Output is correct
18 Correct 1180 ms 49108 KB Output is correct
19 Correct 1252 ms 52772 KB Output is correct
20 Correct 2564 ms 49220 KB Output is correct
21 Correct 347 ms 49040 KB Output is correct
22 Correct 2886 ms 49244 KB Output is correct
23 Correct 291 ms 49140 KB Output is correct
24 Correct 1802 ms 49808 KB Output is correct
25 Correct 3303 ms 49592 KB Output is correct
26 Correct 3020 ms 49684 KB Output is correct
27 Correct 2910 ms 49008 KB Output is correct
28 Correct 1132 ms 49152 KB Output is correct
29 Correct 2122 ms 52144 KB Output is correct
30 Correct 4027 ms 49032 KB Output is correct
31 Correct 3390 ms 49216 KB Output is correct
32 Correct 440 ms 49056 KB Output is correct
33 Correct 801 ms 49160 KB Output is correct
34 Correct 568 ms 49368 KB Output is correct
35 Correct 2063 ms 49864 KB Output is correct
36 Correct 3965 ms 49640 KB Output is correct
37 Correct 2778 ms 50200 KB Output is correct
38 Correct 2880 ms 49452 KB Output is correct
39 Correct 1127 ms 49164 KB Output is correct
40 Correct 2622 ms 61760 KB Output is correct
41 Correct 4519 ms 56568 KB Output is correct
42 Correct 4224 ms 56452 KB Output is correct
43 Correct 780 ms 56556 KB Output is correct
44 Correct 518 ms 58644 KB Output is correct
45 Correct 2316 ms 60164 KB Output is correct
46 Correct 4425 ms 60680 KB Output is correct
47 Correct 4538 ms 60724 KB Output is correct
48 Correct 4564 ms 60284 KB Output is correct
49 Correct 21 ms 48392 KB Output is correct