oj.uz

Submission #962575

# Submission time Handle Problem Language Result Execution time Memory
962575 2024-04-13T20:34:43 Z Leo121 Game (IOI13_game) C++14
100 / 100
 5655 ms 62520 KB 
#include "game.h"
#include <bits/stdc++.h>

#define pb push_back
#define rbg(v) v.rbegin()
#define bg(v) v.begin()
#define all(v) bg(v), v.end()
#define SZ(v) int(v.size())
#define MP make_pair
#define fi first
#define se second
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
#define for0(i, n) forn(i, 0, n - 1)
#define for1(i, n) forn(i, 1, n)
#define fora(i, a, b) for(int i = int(a); i >= int(b); -- i)
#define far0(i, n) fora(i, n - 1, 0)
#define far1(i, n) fora(i, n, 1)
#define foru(i, v) for(auto & i : v)
#define lb lower_bound
#define ub upper_bound
#define SZ(v) int(v.size())
#define ord1(s, n) s + 1, s + int(n) + 1
#define ord0(s, n) s, s + int(n)
#define debug(x) cout << #x << " = " << x << endl

using namespace std;

///#include <bits/extc++.h>
///using namespace __gnu_pbds;
///typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ost;

typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ll> vl;
typedef vector<ii> vii;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef long double ld;
typedef double db;
typedef long long lli;
///typedef __int128 Int;

const int mod1 = 1e9 + 7;
const int mod2 = 998244353;
const int inf = 1e4;

const int MX = 3e5;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
auto randis = uniform_int_distribution<int>(numeric_limits<int>::min(), numeric_limits<int>::max());


struct Node {
	// the value and priority of the node respectively
	int pri, x, y;
	ll val, gcd;
	// pointer to left and right child (NULL means no child)
	Node *left, *right;
	Node(int x, int y, ll v) : val(v), gcd(v), x(x), y(y), pri(randis(rng)), left(NULL), right(NULL){};
};

/**
 * pass in root as pointer, left and right as references
 * to a node pointer so we can modify them
 * (alternatively, we can return left and right pointers
 * as an std::pair)
 */

 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;
}

inline ll gcd(Node * t){return t ? t->gcd : 0;}

void split(Node *root, int x, int y, Node *&left, Node *&right) {
	if (!root) {
		left = right = NULL;
		return;
	}
	if (root->y < y || (root->y == y && root->x <= x)) {
		split(root->right, x, y, root->right, right);
		left = root;
	} else {
		split(root->left, x, y, left, root->left);
		right = root;
	}
	root->gcd = gcd2(gcd2(root->val, gcd(root->left)), gcd(root->right));
}

/**
 * merge left and right pointers into root which
 * is a reference to a pointer to enable
 * modification within the function
 */
void merge(Node *&r, Node *left, Node *right) {
	if (!left || !right) {
		r = left ? left : right;
		return;
	}
	if (left->pri < right->pri) {
		merge(left->right, left->right, right);
		r = left;
	} else {
		merge(right->left, left, right->left);
		r = right;
	}
	r->gcd = gcd2(gcd2(r->val, gcd(r->left)), gcd(r->right));
}


struct nodest{
    int l, r;
    Node * root;
};

nodest st[660000];
int idx = 0;

void pushst(int n, int x, int y, ll val){
    if(!st[n].root){
        st[n].root = new Node(x, y, val);
        return;
    }
    Node *a, *b, *c, *d;
    split(st[n].root, x, y, c, d);
    split(c, x - 1, y, a, b);
    if(!b)
        b = new Node(x, y, val);
    else
        b->gcd = b->val = val;
    merge(st[n].root, a, b);
    merge(st[n].root, st[n].root, d);
}

void updatest(int n, int l, int r, int x, int y, ll val){
    pushst(n, x, y, val);
    if(l == r)
        return;
    int m = (l + r) / 2;
    if(x <= m){
        if(st[n].l == -1){
            st[n].l = ++ idx;
            st[idx].l = st[idx].r = -1;
            st[idx].root = NULL;
        }
        updatest(st[n].l, l, m, x, y, val);
        return;
    }
    if(st[n].r == -1){
        st[n].r = ++ idx;
        st[idx].l = st[idx].r = -1;
        st[idx].root = NULL;
    }
    updatest(st[n].r, m + 1, r, x, y, val);
}

ll querytr(int n, int yi, int yf){
    if(!st[n].root) return 0;
    ll ans = 0;
    Node *a, *b, *c, *d;
    split(st[n].root, -1, yf + 1, c, d);
    split(c, -1, yi, a, b);
    ans = (!b) ? 0 : b->gcd;
    merge(st[n].root, a, b);
    merge(st[n].root, st[n].root, d);
    return ans;
}

ll query(int n, int l, int r, int xi, int xf, int yi, int yf){
    if(n == -1) return 0;
    if(l > xf || r < xi) return 0;
    if(xi <= l && r <= xf) return querytr(n, yi, yf);
    int m = (l + r) / 2;
    return gcd2(query(st[n].l, l, m, xi, xf, yi, yf), query(st[n].r, m + 1, r, xi, xf, yi, yf));
}

int Ri;

void init(int R, int C) {
    st[0].root = NULL;
    st[0].l = -1;
    st[0].r = -1;
    Ri = R;
}

void update(int P, int Q, long long K) {
    updatest(0, 0, Ri - 1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    /* ... */
    return query(0, 0, Ri - 1, P, U, Q, V);
}

Compilation message

game.cpp: In constructor 'Node::Node(int, int, ll)':
game.cpp:59:10: warning: 'Node::gcd' will be initialized after [-Wreorder]
   59 |  ll val, gcd;
      |          ^~~
game.cpp:58:11: warning:   'int Node::x' [-Wreorder]
   58 |  int pri, x, y;
      |           ^
game.cpp:62:2: warning:   when initialized here [-Wreorder]
   62 |  Node(int x, int y, ll v) : val(v), gcd(v), x(x), y(y), pri(randis(rng)), left(NULL), right(NULL){};
      |  ^~~~
game.cpp:58:14: warning: 'Node::y' will be initialized after [-Wreorder]
   58 |  int pri, x, y;
      |              ^
game.cpp:58:6: warning:   'int Node::pri' [-Wreorder]
   58 |  int pri, x, y;
      |      ^~~
game.cpp:62:2: warning:   when initialized here [-Wreorder]
   62 |  Node(int x, int y, ll v) : val(v), gcd(v), x(x), y(y), pri(randis(rng)), left(NULL), right(NULL){};
      |  ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 500 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 476 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 604 ms 11448 KB Output is correct
5 Correct 274 ms 11392 KB Output is correct
6 Correct 956 ms 8888 KB Output is correct
7 Correct 1126 ms 8408 KB Output is correct
8 Correct 787 ms 7816 KB Output is correct
9 Correct 1070 ms 8516 KB Output is correct
10 Correct 938 ms 8328 KB Output is correct
11 Correct 1 ms 440 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 452 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 968 ms 15352 KB Output is correct
13 Correct 2519 ms 10076 KB Output is correct
14 Correct 486 ms 5708 KB Output is correct
15 Correct 2887 ms 11216 KB Output is correct
16 Correct 386 ms 13172 KB Output is correct
17 Correct 1594 ms 10104 KB Output is correct
18 Correct 2759 ms 14356 KB Output is correct
19 Correct 2261 ms 14484 KB Output is correct
20 Correct 2237 ms 13896 KB Output is correct
21 Correct 0 ms 448 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 496 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 622 ms 11388 KB Output is correct
13 Correct 294 ms 11348 KB Output is correct
14 Correct 954 ms 9032 KB Output is correct
15 Correct 1098 ms 8772 KB Output is correct
16 Correct 740 ms 7508 KB Output is correct
17 Correct 1064 ms 8812 KB Output is correct
18 Correct 915 ms 8360 KB Output is correct
19 Correct 933 ms 15228 KB Output is correct
20 Correct 2516 ms 10008 KB Output is correct
21 Correct 471 ms 5692 KB Output is correct
22 Correct 2756 ms 11088 KB Output is correct
23 Correct 270 ms 12884 KB Output is correct
24 Correct 1581 ms 10088 KB Output is correct
25 Correct 2640 ms 14248 KB Output is correct
26 Correct 2266 ms 14380 KB Output is correct
27 Correct 2240 ms 13784 KB Output is correct
28 Correct 772 ms 35100 KB Output is correct
29 Correct 1284 ms 37904 KB Output is correct
30 Correct 3538 ms 29492 KB Output is correct
31 Correct 3029 ms 24672 KB Output is correct
32 Correct 665 ms 10932 KB Output is correct
33 Correct 948 ms 11492 KB Output is correct
34 Correct 325 ms 31568 KB Output is correct
35 Correct 1721 ms 23120 KB Output is correct
36 Correct 3057 ms 35664 KB Output is correct
37 Correct 2453 ms 35876 KB Output is correct
38 Correct 2551 ms 35288 KB Output is correct
39 Correct 2137 ms 28832 KB Output is correct
40 Correct 1 ms 348 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 448 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 448 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 592 ms 11560 KB Output is correct
13 Correct 264 ms 11248 KB Output is correct
14 Correct 948 ms 8872 KB Output is correct
15 Correct 1084 ms 8568 KB Output is correct
16 Correct 738 ms 7584 KB Output is correct
17 Correct 1069 ms 8672 KB Output is correct
18 Correct 944 ms 8352 KB Output is correct
19 Correct 922 ms 15444 KB Output is correct
20 Correct 2632 ms 10164 KB Output is correct
21 Correct 481 ms 5788 KB Output is correct
22 Correct 2885 ms 11060 KB Output is correct
23 Correct 365 ms 12880 KB Output is correct
24 Correct 1566 ms 10304 KB Output is correct
25 Correct 2673 ms 14156 KB Output is correct
26 Correct 2241 ms 14628 KB Output is correct
27 Correct 2233 ms 13672 KB Output is correct
28 Correct 850 ms 35108 KB Output is correct
29 Correct 1357 ms 37932 KB Output is correct
30 Correct 3601 ms 29560 KB Output is correct
31 Correct 2915 ms 24976 KB Output is correct
32 Correct 671 ms 10796 KB Output is correct
33 Correct 993 ms 11556 KB Output is correct
34 Correct 407 ms 31576 KB Output is correct
35 Correct 1656 ms 23184 KB Output is correct
36 Correct 3260 ms 35656 KB Output is correct
37 Correct 2562 ms 35824 KB Output is correct
38 Correct 2535 ms 35192 KB Output is correct
39 Correct 1172 ms 60368 KB Output is correct
40 Correct 2280 ms 62520 KB Output is correct
41 Correct 5655 ms 55052 KB Output is correct
42 Correct 4898 ms 44256 KB Output is correct
43 Correct 647 ms 57408 KB Output is correct
44 Correct 1148 ms 12344 KB Output is correct
45 Correct 2149 ms 28828 KB Output is correct
46 Correct 4091 ms 61208 KB Output is correct
47 Correct 3877 ms 61404 KB Output is correct
48 Correct 3815 ms 61024 KB Output is correct
49 Correct 0 ms 348 KB Output is correct