oj.uz

Submission #402777

# Submission time Handle Problem Language Result Execution time Memory
402777 2021-05-12T10:57:51 Z ACmachine Game (IOI13_game) C++17
100 / 100
 7649 ms 84792 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U> using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vi;
typedef vector<ll> vll;

#define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
#define FORD(i,j,k,in) for(int i=(j); i >=(k);i-=in)
#define REP(i,b) FOR(i,0,b,1)
#define REPD(i,b) FORD(i,b,0,1)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define MANY_TESTS int tcase; cin >> tcase; while(tcase--)

const double EPS = 1e-9;
const int MOD = 1e9+7;
const ll INFF = 1e18;
const int INF = 1e9;
const ld PI = acos((ld)-1);
const vi dy = {1, 0, -1, 0, -1, 1, 1, -1};
const vi dx = {0, 1, 0, -1, -1, 1, -1, 1};

void DBG(){cout << "]" << endl;}
template<typename T, typename ...U> void DBG(const T& head, const U... args){ cout << head << "; "; DBG(args...); }
#define dbg(...) cout << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__);
#define chk() cout << "Check at line(" << __LINE__ << ") hit." << endl;

template<class T, unsigned int U>
ostream& operator<<(ostream& out, const array<T, U> &v){out << "[";  REP(i, U) out << v[i] << ", ";  out << "]"; return out;}
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "[" << par.first << ";" << par.second << "]"; return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template<class T>
ostream& operator<<(ostream& out, const vector<T> &v){ out << "[";  REP(i, v.size()) out << v[i] << ", ";  out << "]"; return out;}

template<class T>
istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; }



long long gcd2(long long X, long long Y) {
    if(X == 0) return Y;
    if(Y == 0) return X;
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct treap{
    ll val; int key;
    ll res;
    int y;
    array<treap*, 2> ch;
    treap(int _key, ll _val) : key(_key), val(_val), y(rand()), res(val){
        ch = {NULL, NULL};
    }
};


void recalc(treap *t){
    if(t == NULL) return;
    t->res = t->val;
    REP(i, 2){
        if(t->ch[i] != NULL)
            t->res = gcd2(t->res, t->ch[i]->res);
    }
    return;
}
ll getres(treap* t){
    return (t == NULL ? 0 : t->res);
}
pair<treap*, treap*> split(treap* t, int key){ // all < key
    if(t == NULL)
        return {NULL, NULL};
    if(t->key < key){
        auto pa = split(t->ch[1], key);
        t->ch[1] = pa.ff;
        recalc(t);
        return {t, pa.ss};
    }
    else{
        auto pa = split(t->ch[0], key);
        t->ch[0] = pa.ss;
        recalc(t);
        return {pa.ff, t};
    }
}
treap* merge(treap* f, treap *s){
    if(f == NULL) return s;
    if(s == NULL) return f;
    if(f->y >= s->y){
        f->ch[1] = merge(f->ch[1], s);
        recalc(f);
        return f;
    }
    else{
        s->ch[0] = merge(f, s->ch[0]);
        recalc(s);
        return s;
    }
}
treap* insert(treap* t, treap *s){ // second add to treapu t
    if(t == NULL) {
        return s;
    }
    auto paf = split(t, s->key);
    auto pas = split(paf.ss, s->key + 1);
    t = merge(paf.ff, merge(s, pas.ss));
    return t;
}
ll query_treap(treap* &t, int l, int r){
    if(t == NULL) return 0ll;
    auto pa = split(t, l);
    auto pa2 = split(pa.ss, r);
    ll res = getres(pa2.ff);
    t = merge(pa.ff, merge(pa2.ff, pa2.ss));
    return res;
}
// wohoo correct treap
// dynamic segtree

struct segtree2d{
    vector<treap*> tree;
    vector<int> lch; // left and right child
    vector<int> rch;
    int n;
    void create_node(){
        treap* s = new treap(-1, 0);
        tree.pb(s);
        lch.pb(-1);
        rch.pb(-1);
    }
    void pull(int id, int x){
        ll fv = 0, sv = 0;
        if(lch[id] != -1){
            fv = query_treap(tree[lch[id]], x, x + 1);
        }
        if(rch[id] != -1){
            sv = query_treap(tree[rch[id]], x, x + 1);
        }
        tree[id] = insert(tree[id], new treap(x, gcd2(fv, sv)));
    }
    segtree2d(){}
    segtree2d(int sz){
        n = 1;
        while(n <= sz)
            n *= 2;
        create_node();
    }
    void upd(int row, int col, int beg, int end, int v, ll value){
        if(beg == row && beg + 1 == end){
            treap* s = new treap(col, value);
            tree[v] = insert(tree[v], s);
            return;
        }
        int mid = (beg + end) >> 1;
        if(row < mid){
            if(lch[v] == -1){
                create_node();
                int id = (int)tree.size() - 1;
                lch[v] = id;
            }
            upd(row, col, beg, mid, lch[v], value);
        }
        else{
            if(rch[v] == -1){
                create_node();
                int id = (int)tree.size() - 1;
                rch[v] = id;
            }
            upd(row, col, mid, end, rch[v], value);
        }
        pull(v, col);
    }
    ll query(int x1, int x2, int y1, int y2, int beg, int end, int v){
        if(beg >= y1 && end <= y2){
            return query_treap(tree[v], x1, x2);
        }
        if(beg >= y2 || end <= y1)
            return 0ll;
        int mid = (beg + end) >> 1;
        ll tmf = 0;
        if(lch[v] != -1)
            tmf = query(x1, x2, y1, y2, beg, mid, lch[v]);
        ll tms = 0;
        if(rch[v] != -1)
            tms = query(x1, x2, y1, y2, mid, end, rch[v]);
        return gcd2(tmf, tms);
    }
};
segtree2d st;
void init(int R, int C) {
    srand(time(NULL));
    st = segtree2d(R);
}

void update(int P, int Q, long long K) {
    st.upd(P, Q, 0, st.n, 0, K);
}

long long calculate(int P, int Q, int U, int V) { // xrange[Q, V + 1); yrange[P, U + 1)
    ll res = st.query(Q, V + 1, P, U + 1, 0, st.n, 0);
    return res;
}

Compilation message

game.cpp: In constructor 'treap::treap(int, ll)':
game.cpp:73:17: warning: 'treap::key' will be initialized after [-Wreorder]
   73 |     ll val; int key;
      |                 ^~~
game.cpp:73:8: warning:   'll treap::val' [-Wreorder]
   73 |     ll val; int key;
      |        ^~~
game.cpp:77:5: warning:   when initialized here [-Wreorder]
   77 |     treap(int _key, ll _val) : key(_key), val(_val), y(rand()), res(val){
      |     ^~~~~
game.cpp:75:9: warning: 'treap::y' will be initialized after [-Wreorder]
   75 |     int y;
      |         ^
game.cpp:74:8: warning:   'll treap::res' [-Wreorder]
   74 |     ll res;
      |        ^~~
game.cpp:77:5: warning:   when initialized here [-Wreorder]
   77 |     treap(int _key, ll _val) : key(_key), val(_val), y(rand()), res(val){
      |     ^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 975 ms 7384 KB Output is correct
5 Correct 522 ms 7712 KB Output is correct
6 Correct 1526 ms 4636 KB Output is correct
7 Correct 1750 ms 4208 KB Output is correct
8 Correct 1155 ms 3328 KB Output is correct
9 Correct 1664 ms 4332 KB Output is correct
10 Correct 1404 ms 4156 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1825 ms 12232 KB Output is correct
13 Correct 3604 ms 11780 KB Output is correct
14 Correct 633 ms 12372 KB Output is correct
15 Correct 3944 ms 12620 KB Output is correct
16 Correct 1179 ms 12672 KB Output is correct
17 Correct 2354 ms 9192 KB Output is correct
18 Correct 4287 ms 13000 KB Output is correct
19 Correct 3561 ms 13124 KB Output is correct
20 Correct 3377 ms 12548 KB Output is correct
21 Correct 1 ms 204 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 968 ms 7448 KB Output is correct
13 Correct 545 ms 7824 KB Output is correct
14 Correct 1534 ms 4392 KB Output is correct
15 Correct 1786 ms 4232 KB Output is correct
16 Correct 1154 ms 3304 KB Output is correct
17 Correct 1740 ms 4252 KB Output is correct
18 Correct 1472 ms 3952 KB Output is correct
19 Correct 1859 ms 12260 KB Output is correct
20 Correct 3750 ms 12156 KB Output is correct
21 Correct 619 ms 13172 KB Output is correct
22 Correct 3838 ms 13248 KB Output is correct
23 Correct 1337 ms 13120 KB Output is correct
24 Correct 2424 ms 10304 KB Output is correct
25 Correct 4660 ms 14640 KB Output is correct
26 Correct 3791 ms 14808 KB Output is correct
27 Correct 3454 ms 14232 KB Output is correct
28 Correct 1602 ms 44720 KB Output is correct
29 Correct 2973 ms 47336 KB Output is correct
30 Correct 5020 ms 34920 KB Output is correct
31 Correct 4650 ms 33336 KB Output is correct
32 Correct 834 ms 29508 KB Output is correct
33 Correct 1273 ms 29540 KB Output is correct
34 Correct 1986 ms 41352 KB Output is correct
35 Correct 2891 ms 28216 KB Output is correct
36 Correct 5752 ms 45564 KB Output is correct
37 Correct 4609 ms 45496 KB Output is correct
38 Correct 4721 ms 45068 KB Output is correct
39 Correct 4131 ms 37460 KB Output is correct
40 Correct 1 ms 204 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 224 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1063 ms 7460 KB Output is correct
13 Correct 526 ms 7740 KB Output is correct
14 Correct 1524 ms 4520 KB Output is correct
15 Correct 1746 ms 4384 KB Output is correct
16 Correct 1138 ms 3376 KB Output is correct
17 Correct 1665 ms 4344 KB Output is correct
18 Correct 1444 ms 3884 KB Output is correct
19 Correct 1786 ms 12236 KB Output is correct
20 Correct 3620 ms 11968 KB Output is correct
21 Correct 628 ms 13032 KB Output is correct
22 Correct 3972 ms 13244 KB Output is correct
23 Correct 1274 ms 13128 KB Output is correct
24 Correct 2394 ms 10368 KB Output is correct
25 Correct 4426 ms 14612 KB Output is correct
26 Correct 3712 ms 14848 KB Output is correct
27 Correct 3467 ms 14036 KB Output is correct
28 Correct 1575 ms 44680 KB Output is correct
29 Correct 2782 ms 47376 KB Output is correct
30 Correct 4860 ms 34976 KB Output is correct
31 Correct 4500 ms 33340 KB Output is correct
32 Correct 838 ms 29504 KB Output is correct
33 Correct 1268 ms 29544 KB Output is correct
34 Correct 1879 ms 41212 KB Output is correct
35 Correct 2900 ms 28272 KB Output is correct
36 Correct 5544 ms 45188 KB Output is correct
37 Correct 4485 ms 45392 KB Output is correct
38 Correct 4747 ms 44816 KB Output is correct
39 Correct 2267 ms 82792 KB Output is correct
40 Correct 4740 ms 84792 KB Output is correct
41 Correct 7649 ms 66876 KB Output is correct
42 Correct 7142 ms 63036 KB Output is correct
43 Correct 3062 ms 79752 KB Output is correct
44 Correct 1367 ms 53224 KB Output is correct
45 Correct 3686 ms 37564 KB Output is correct
46 Correct 7387 ms 83788 KB Output is correct
47 Correct 7413 ms 83804 KB Output is correct
48 Correct 7137 ms 83416 KB Output is correct
49 Correct 1 ms 204 KB Output is correct