Submission #1025756

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

game

#include <bits/stdc++.h>
#include "game.h"
using namespace std;
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int,int>
#define st first
#define nd second
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define ll long long
#define MAXN 200005


const int M = 1e9;

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 Node{
	ll valy;
	int XL, XR, YR, YL;
	Node(){
		XL = XR = YL = YR = -1;
		valy = 0;
	}
};

vector<Node> A;

void pull_y(int node){
	ll lft = 0, rgt = 0;
	if (A[node].YL != -1) lft = A[A[node].YL].valy;
	if (A[node].YR != -1) rgt = A[A[node].YR].valy;
	A[node].valy = gcd2(lft, rgt);
}

void pull_x(int node){
	ll lft = 0, rgt = 0;
	if (A[node].XL != -1) lft = A[A[node].XL].valy;
	if (A[node].XR != -1) rgt = A[A[node].XR].valy;
	A[node].valy = gcd2(lft, rgt);
}

typedef Node* pnode;



struct SegTree{
	int root = 0;
	
	int R, C;

	int create(){
		Node tmp = *(new Node());
		int ans = (int)A.size();
		A.pb(tmp);
		return ans;
	}

	SegTree(int r, int c){
		root = create();
		R = r, C = c;
	}

	void update_y(int node, int l, int r, int a, int b, int sl, ll val){
		if (l > sl || r < sl) return;
		if (l == r){
			if (a == b) A[node].valy = val;
			else {
				pull_x(node);
			}
			return;
		}

		int mid = (l + r) / 2;

		if (sl <= mid){
			if (A[node].YL == -1){
				A[node].YL = create();
			}
			if (A[node].XL != -1) A[A[node].YL].XL = A[A[node].XL].YL;
			if (A[node].XR != -1) A[A[node].YL].XR = A[A[node].XR].YL;
			update_y(A[node].YL, l, mid, a, b, sl, val);
		}

		else{
			if (A[node].YR == -1){
				A[node].YR = create();
			}
			if (A[node].XL != -1) A[A[node].YR].XL = A[A[node].XL].YR;
			if (A[node].XR != -1) A[A[node].YR].XR = A[A[node].XR].YR;
			update_y(A[node].YR, mid + 1, r, a, b, sl, val);
		}

		pull_y(node);
	}

	void update_x(int node, int l, int r, int x, int y, ll val){
		if (l > x || r < x) return;
		
		if (l != r){
			int mid = (l + r) / 2;
			if (x <= mid){
				if (A[node].XL == -1){
					A[node].XL = create();
				}
				update_x(A[node].XL, l, mid, x, y, val);
			}

			else{
				if (A[node].XR == -1){
					A[node].XR = create();
				}
				update_x(A[node].XR, mid + 1, r, x, y, val);
			}
		}

		update_y(node, 1, C, l, r, y, val);
	}


	void update(int x, int y, ll val){
		update_x(root, 1, R, x, y, val);
	}


	ll query_y(int node, int l, int r, int sl, int sr){
		if (l > sr || r < sl) return 0;
		if (l >= sl && r <= sr) return A[node].valy;
		ll lft = 0, rgt = 0;
		int mid = (l + r) / 2;
		if (A[node].YL != -1 && sl <= mid) lft = query_y(A[node].YL, l, mid, sl, sr);
		if (A[node].YR != -1 && sr > mid) rgt = query_y(A[node].YR, mid + 1, r, sl, sr);
		return gcd2(lft, rgt);
	}

	ll query_x(int node, int l, int r, int a, int b, int c, int d){
		if (l > b || r < a) return 0;
		if (l >= a && r <= b) {
			ll val = query_y(node, 1, C, c, d);
			return val;
		}
		ll lft = 0, rgt = 0;
		int mid = (l + r) / 2;
		if (A[node].XL != -1 && a <= mid){
			lft = query_x(A[node].XL, l, mid, a, b, c, d);
		}

		if (A[node].XR != -1 && b > mid){
			rgt = query_x(A[node].XR, mid + 1, r, a, b, c, d);
		}
		return gcd2(lft, rgt);
	}

	ll query(int a, int b, int c, int d){
		return query_x(root, 1, R, a, b, c, d);
	}
};



SegTree *t;

void init(int R, int C) {
    t = new SegTree(R, C);
}

void update(int P, int Q, long long K) {
    t->update(P + 1, Q + 1, K);
}

long long calculate(int P, int Q, int U, int V) {
    P++, Q++, U++, V++;
    return t->query(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;

	freopen("output.txt", "w", stdout);

	FILE *f = fopen("input.txt", "r");
	if (!f)
		fail("Failed to open input file.");

	res = fscanf(f, "%d", &R);
	res = fscanf(f, "%d", &C);
	res = fscanf(f, "%d", &N);

    init(R, C);

	for (i = 0; i < N; i++) {
        res = fscanf(f, "%d", &type);
        if (type == 1) {
		    res = fscanf(f, "%d%d%lld", &P, &Q, &K);
            update(P, Q, K);
        } else if (type == 2) {
		    res = fscanf(f, "%d%d%d%d", &P, &Q, &U, &V);
            printf("%lld\n", calculate(P, Q, U, V));
        } else
			fail("Invalid action type in input file.");
	}
	fclose(f);

	return 0;
}
*/

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