Submission #1079932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079932		dozer	Game (IOI13_game)	C++14	0 / 100	1 ms	348 KiB

game

#include <bits/stdc++.h>
#include "game.h"
using namespace std;
#define sp " "
#define endl "\n";
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define ll long long

const int modulo = 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;
}
 

struct Treap{
	struct Node{
		ll h, b;
		Node *l, *r;
		ll val;
		ll gcdd;

		Node(ll ind, ll v){
			val = v;
			gcdd = v;
			b = ind;
			h = rand();
			l = r = NULL;
		};

		void pull(){
			gcdd = val;
			if (l != NULL) gcdd = gcd2(gcdd, l->gcdd);
			if (r != NULL) gcdd = gcd2(gcdd, r->gcdd);
		}
	};

	typedef Node* pnode;

	pnode root;

	Treap(){
		root = NULL;
	}

	void split(pnode node, pnode &L, pnode &R, ll val){
		if (node == NULL) return;
		if (node->b <= val){
			L = node;
			pnode tmp = NULL;
			split(node->r, tmp, R, val);
			L->r = tmp;
		}
		else{
			R = node;
			pnode tmp = NULL;
			split(node->l, L, tmp, val);
			R->l = tmp;
		}
		if (L != NULL) L->pull();
		if (R != NULL) R->pull();
	}

	void merge(pnode L, pnode R, pnode &res){
		if (L == NULL){
			res = R;
			return;
		}
		if (R == NULL){
			res = L;
			return;
		}
		if (L->h > R->h){
			pnode tmp = NULL;;
			merge(L->r, R, tmp);
			L->r = tmp;
			res = L;
		}
		else{
			pnode tmp = NULL;
			merge(L, R->l, tmp);
			R->l = tmp;
			res = R;
		}
		if (res != NULL) res->pull();
	}

	ll query(ll l, ll r){
		pnode a = NULL, b = NULL, c = NULL, d = NULL;
		split(root, a, b, l - 1);
		split(b, c, d, r);
		ll ans = 0;
		if (c != NULL) ans = c->gcdd;
		pnode tmp;
		merge(a, c, tmp);
		pnode tmp2;
		merge(tmp, d, root);
		return ans;
	}

	void update(ll ind, ll val){
		pnode a = NULL, b = NULL, c = NULL, d = NULL;
		split(root, a, b, ind - 1);
		split(b, c, d, ind);
		if (c == NULL) c = new Node(ind, val);
		c->val = val;
		c->gcdd = val;
		pnode tmp = NULL;
		merge(a, c, tmp);
		merge(tmp, d, root);
	}
};


struct SegTree{
	struct Node{
		Node *l, *r;
		Treap *t;
		Node(){
			t = new Treap();
			l = r = NULL;
		}
	};


	typedef Node* pnode;
	ll r;

	pnode root;
	SegTree(){
		root = new Node();
	}

	SegTree(ll R){
		root = new Node();
		r = R;
		srand(time(NULL));
	}

	void update(pnode node, ll l, ll r, ll sx, ll sy, ll val){
		node->t->update(sy, val);
		if (l == r) return;
		ll mid = (l + r) / 2;
		if (sx <= mid){
			if (node->l == NULL) node->l = new Node();
			update(node->l, l, mid, sx, sy, val);
		}
		else{
			if (node->r == NULL) node ->r = new Node();
			update(node->r, mid + 1, r, sx, sy, val);
		}
	}

	ll query(pnode node, ll l, ll r, ll a, ll b, ll c, ll d){
		if (l > b || r < a) return 0;
		if (l >= a && r <= b) return node->t->query(c, d);
		ll mid = (l + r) / 2;
		ll ans = 0;
		if (a <= mid && node->l != NULL){
			ans = gcd2(ans, query(node->l, l, mid, a, b, c, d));
		}
		if (b > mid && node->r != NULL){
			ans = gcd2(ans, query(node->r, mid + 1, r, a, b, c, d));
		}
		return ans;
	}

	void update_util(ll sx, ll sy, ll val){
		update(root, 1, r, sx, sy, val);
	}

	ll query_util(ll a, ll b, ll c, ll d){
		return query(root, 1, r, a, b, c, d);
	}
};

ll r, c;
SegTree *t;

void init(int R, int C) {
    t = new SegTree(R);
    r = R, c = C;
}
 
void update(int P, int Q, long long K) {
    t->update_util(P + 1, Q + 1, K);
}
 
long long calculate(int P, int Q, int U, int V) {
    P++, Q++, U++, V++;
    return t->query_util(P, U, Q, V);
}
 
 
/*
#define fail(s, x...) do { \
		fprintf(stderr, s "\n", ## x); \
		exit(1); \
	} while(0)
 
#define MAX_SIZE 1000000000
#define MAX_N 272000
 
int main() {
	int R, C, N;
    int P, Q, U, V;
    long long K;
    int i, type;
	int res;
 
 
	res = scanf("%d", &R);
	res = scanf("%d", &C);
	res = scanf("%d", &N);
 
    init(R, C);
 
	for (i = 0; i < N; i++) {
        res = scanf("%d", &type);
        if (type == 1) {
		    res = scanf("%d%d%lld", &P, &Q, &K);
            update(P, Q, K);
        } else if (type == 2) {
		    res = scanf("%d%d%d%d", &P, &Q, &U, &V);
           	printf("%lld\n", calculate(P, Q, U, V));
        } else{
        	printf("%d\n", type);
			fail("Invalid action type in input file.");
        }
	}
 	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
	return 0;
}
*/

Compilation message (stderr)

game.cpp: In member function 'long long int Treap::query(long long int, long long int)':
game.cpp:107:9: warning: unused variable 'tmp2' [-Wunused-variable]
  107 |   pnode tmp2;
      |         ^~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20