Submission #789533

#	Time	Username	Problem	Language	Result	Execution time	Memory
789533		MODDI	Game (IOI13_game)	C++14	0 / 100	238 ms	14304 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
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 segtree{
	struct Node{
		ll v,flag;
		Node* l, *r;
		Node(ll a, Node* _l, Node* _r) : v(a), l(_l), r(_r){
			flag = -1;
		}
	};
	int size;
	Node* root, *null;
	void init(int n){
		size = 1;
		while(size < n)	size*=2;
		null = new Node(0, nullptr, nullptr);
		null->l = null->r = null;
		root = null;
	}
	Node *update(Node* node, int l, int r, int i, ll v){
		if(node == null)	node = new Node(0, null, null);
		if(l+1 == r){
			node->v = v;
			return node;
		}
		int mid = (l + r) / 2;
		if(node->flag==-1 || node->flag == i){
			node->flag = i;
			node->v = v;
			return node;
		}
		else if(node->flag != -2){
			if(node->flag < mid)
				node->l = update(node->l, l, mid, node->flag, node->v);
			else
				node->r = update(node->r, mid, r, node->flag, node->v);
				
			node->flag = -2;
		}
		if(i < mid){
			node->l = update(node->l, l, mid, i, v);
		}
		else
			node->r = update(node->r, mid, r, i, v);
	
		node->v = gcd2(node->l->v, node->r->v);
		return node;
	}
	void update(int i, ll v){
		root = update(root, 0, size, i, v);
	}
	ll query(Node* node, int l, int r, int L, int R){
		if(l >= R || L >= r || node == null)	return 0;
		if(node->flag >= 0){
			int pom = node->flag;
			if(pom >= l && pom < r)	return node->v;
			else return 0;
		}
		if(l <= L && R <= r){
			ll ret = node->v;
			return ret;
		}
		int mid = (L + R) / 2;
		ll left = query(node->l, l, r, L, mid);
		ll right = query(node->r, l, r, mid, r);
		return gcd2(left, right);
	}
	ll query(int l, int r){
		return query(root, l, r, 0, size);
	}	
};
struct seg2D{
	struct Node{
		segtree col;
		Node*l , *r;
		Node(int sz, Node* a, Node* b) : l(a), r(b){ col.init(sz);}
	};
	Node* root, *null;
	int row_size, col_size;
	void init(int n, int m){
		row_size = 1;
		while(row_size<n)	row_size*=2;
		col_size = m;
		null = new Node(col_size, nullptr, nullptr);
		null->l= null->r = null;
		root = null;
	}
	ll query(Node* node, int l1, int r1, int l2, int r2, int L, int R){
		if(l1 >= R || L >= r1 || node == null)	return 0;
		if(l1 <= L && R <= r1){
			return node->col.query(l2, r2);
		}
		int mid = (L + R) / 2;
		ll left = query(node->l, l1, r1, l2, r2, L, mid);
		ll right = query(node->r, l1, r1, l2, r2, mid, R);
		return gcd2(left, right);
	}
	ll query(int l1, int r1, int l2, int r2){
		return query(root, l1, r1, l2, r2, 0, row_size);
	}
	Node* update(Node* node, int l, int r, int L, int R, ll v){
		if(node == null) node = new Node(col_size, null, null);
		if(L+1 == R){
			node->col.update(r, v);
			return node;
		}
		int mid = (L + R) / 2;
		if(l < mid){
			node->l = update(node->l, l, r, L, mid, v);
		}
		else
			node->r = update(node->r, l, r, mid, R, v);
			
		ll new_v = gcd2(node->l->col.query(r, r+1), node->r->col.query(r, r+1));
		node->col.update(r, new_v);
		return node;
	}
	void update(int l, int r, ll v){
		root = update(root, l, r, 0, row_size, v);
	}
};
seg2D mat;
void init(int R, int C) {
   	mat.init(R, C);
}

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

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

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