Submission #962569

#	Time	Username	Problem	Language	Result	Execution time	Memory
962569		Leo121	Game (IOI13_game)	C++14	0 / 100	1 ms	600 KiB

game

#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(gcd(root), 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(gcd(r), 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 (stderr)

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: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20