oj.uz

Submission #373745

# Submission time Handle Problem Language Result Execution time Memory
373745 2021-03-05T15:07:27 Z cheissmart Game (IOI13_game) C++14
100 / 100
 5939 ms 119748 KB 
#include "game.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define V vector
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "LINE(" << __LINE__ << ") -> " << #x << " is " << (x) << endl
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
 
const int INF = 1e9 + 7;

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

int R, C;

struct seg_y {
    struct node {
        node *l, *r;
        ll g; // gcd
        int lz_pos;
        ll lz_val;
        bool islz;
        node() {
            l = r = nullptr;
            g = lz_pos = lz_val = 0;
            islz = false;
        }
        node(int _lz_pos, ll _lz_val) {
            l = r = nullptr;
            lz_pos = _lz_pos;
            g = lz_val = _lz_val;
            islz = true;   
        }
    };
    node* root;
    seg_y() {
        root = nullptr;
    }
    ll g(node* t) {
        return t ? t -> g : 0LL;
    }
    void pull(node* t) {   
        t -> g = gcd2(g(t -> l), g(t -> r));
    }
    void upd(node* &t, int y, ll val, int tl = 0, int tr = C) {
        if(!t) {
            t = new node(y, val);
            return;
        }
        int tm = (tl + tr) / 2;
        if(t -> islz) {
            if(t -> lz_pos == y) {
                t -> g = t -> lz_val = val;
                return;
            }
            if(t -> lz_pos < tm) t -> l = new node(t -> lz_pos, t -> lz_val);
            else t -> r = new node(t -> lz_pos, t -> lz_val);
            t -> islz = false;
        }
        if(y < tm) upd(t -> l, y, val, tl, tm);
        else upd(t -> r, y, val, tm, tr);
        pull(t);
    }
    ll qry(node* t, int l, int r, int tl = 0, int tr = C) {
        if(!t) return 0;
        if(t -> islz) {
            if(l <= t -> lz_pos && t -> lz_pos < r) return t -> lz_val;
            else return 0;
        }
        if(l <= tl && tr <= r) return t -> g;
        int tm = (tl + tr) / 2;
        ll g = 0;
        if(l < tm) g = gcd2(g, qry(t -> l, l, r, tl, tm));
        if(r > tm) g = gcd2(g, qry(t -> r, l, r, tm, tr));
        return g;
    }
    void upd(int y, ll val) {
        upd(root, y, val);
    }
    ll qry(int l, int r) {
        return qry(root, l, r);
    }
    ll qry(int y) {
        return qry(y, y + 1);
    }
};

struct seg_x {
    struct node {
        node *l, *r;
        seg_y seg;
        node() {
            l = r = nullptr;
        }
    };
    node* root;
    void pull(node* t, int y) {
        ll g = 0;
        if(t -> l) g = gcd2(g, t -> l -> seg.qry(y));
        if(t -> r) g = gcd2(g, t -> r -> seg.qry(y));
        t -> seg.upd(y, g);
    }
    void upd(node* &t, int x, int y, ll val, int tl = 0, int tr = R) {
        if(!t) t = new node();
        if(tr - tl == 1) {
            t -> seg.upd(y, val);
            return;
        }
        int tm = (tl + tr) / 2;
        if(x < tm) upd(t -> l, x, y, val, tl, tm);
        else upd(t -> r, x, y, val, tm, tr);
        pull(t, y);
    }
    void upd(int x, int y, ll val) {
        upd(root, x, y, val);
    }
    ll qry(node* t, int xl, int xr, int yl, int yr, int tl = 0, int tr = R) {
        if(!t) return 0;
        if(xl <= tl && tr <= xr) return t -> seg.qry(yl, yr);
        int tm = (tl + tr) / 2;
        ll g = 0;
        if(xl < tm) g = gcd2(g, qry(t -> l, xl, xr, yl, yr, tl, tm));
        if(xr > tm) g = gcd2(g, qry(t -> r, xl, xr, yl, yr, tm, tr));
        return g;
    }
    ll qry(int xl, int xr, int yl, int yr) {
        return qry(root, xl, xr, yl, yr);
    }
} seg;

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

void update(int P, int Q, long long K) {
    seg.upd(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return seg.qry(P, U + 1, Q, V + 1);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 555 ms 11244 KB Output is correct
5 Correct 423 ms 11372 KB Output is correct
6 Correct 489 ms 8172 KB Output is correct
7 Correct 578 ms 7916 KB Output is correct
8 Correct 352 ms 5612 KB Output is correct
9 Correct 570 ms 8044 KB Output is correct
10 Correct 531 ms 7788 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 935 ms 15588 KB Output is correct
13 Correct 1537 ms 7852 KB Output is correct
14 Correct 307 ms 1516 KB Output is correct
15 Correct 1828 ms 10092 KB Output is correct
16 Correct 230 ms 15212 KB Output is correct
17 Correct 832 ms 9196 KB Output is correct
18 Correct 1716 ms 15612 KB Output is correct
19 Correct 1399 ms 15596 KB Output is correct
20 Correct 1293 ms 15320 KB Output is correct
21 Correct 1 ms 364 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 551 ms 11116 KB Output is correct
13 Correct 417 ms 11500 KB Output is correct
14 Correct 486 ms 8300 KB Output is correct
15 Correct 561 ms 8044 KB Output is correct
16 Correct 366 ms 5760 KB Output is correct
17 Correct 537 ms 8312 KB Output is correct
18 Correct 497 ms 7660 KB Output is correct
19 Correct 950 ms 15716 KB Output is correct
20 Correct 1529 ms 8104 KB Output is correct
21 Correct 305 ms 1388 KB Output is correct
22 Correct 1839 ms 9876 KB Output is correct
23 Correct 237 ms 14828 KB Output is correct
24 Correct 807 ms 9184 KB Output is correct
25 Correct 1691 ms 15540 KB Output is correct
26 Correct 1315 ms 15680 KB Output is correct
27 Correct 1260 ms 15088 KB Output is correct
28 Correct 648 ms 49132 KB Output is correct
29 Correct 1581 ms 51616 KB Output is correct
30 Correct 4561 ms 54884 KB Output is correct
31 Correct 4251 ms 42868 KB Output is correct
32 Correct 673 ms 10860 KB Output is correct
33 Correct 849 ms 15728 KB Output is correct
34 Correct 308 ms 45164 KB Output is correct
35 Correct 1161 ms 29640 KB Output is correct
36 Correct 2397 ms 49372 KB Output is correct
37 Correct 1815 ms 49644 KB Output is correct
38 Correct 1811 ms 49104 KB Output is correct
39 Correct 1518 ms 40172 KB Output is correct
40 Correct 1 ms 364 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 562 ms 11500 KB Output is correct
13 Correct 406 ms 11372 KB Output is correct
14 Correct 507 ms 8232 KB Output is correct
15 Correct 582 ms 7924 KB Output is correct
16 Correct 339 ms 5612 KB Output is correct
17 Correct 565 ms 8044 KB Output is correct
18 Correct 525 ms 7568 KB Output is correct
19 Correct 924 ms 15852 KB Output is correct
20 Correct 1525 ms 8032 KB Output is correct
21 Correct 299 ms 1516 KB Output is correct
22 Correct 1824 ms 10144 KB Output is correct
23 Correct 238 ms 15084 KB Output is correct
24 Correct 819 ms 9232 KB Output is correct
25 Correct 1639 ms 15812 KB Output is correct
26 Correct 1354 ms 15768 KB Output is correct
27 Correct 1285 ms 15168 KB Output is correct
28 Correct 647 ms 49004 KB Output is correct
29 Correct 1548 ms 51612 KB Output is correct
30 Correct 4551 ms 54632 KB Output is correct
31 Correct 4280 ms 43068 KB Output is correct
32 Correct 668 ms 10996 KB Output is correct
33 Correct 827 ms 15596 KB Output is correct
34 Correct 323 ms 45036 KB Output is correct
35 Correct 1096 ms 29804 KB Output is correct
36 Correct 2344 ms 49236 KB Output is correct
37 Correct 1798 ms 49748 KB Output is correct
38 Correct 1837 ms 49088 KB Output is correct
39 Correct 889 ms 119748 KB Output is correct
40 Correct 2598 ms 97104 KB Output is correct
41 Correct 5939 ms 110036 KB Output is correct
42 Correct 5594 ms 84664 KB Output is correct
43 Correct 576 ms 91840 KB Output is correct
44 Correct 930 ms 11440 KB Output is correct
45 Correct 1474 ms 40296 KB Output is correct
46 Correct 3040 ms 95852 KB Output is correct
47 Correct 2925 ms 96108 KB Output is correct
48 Correct 2854 ms 95584 KB Output is correct
49 Correct 1 ms 364 KB Output is correct