Submission #1216575

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216575		nishkarsh	Game (IOI13_game)	C++20	100 / 100	4805 ms	60400 KiB

game

#include "game.h"

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define vt vector
using namespace std;
 
ll powmod(ll base,ll exponent,ll mod){
	ll ans=1;
	if(base<0) base+=mod;
	while(exponent){
		if(exponent&1)ans=(ans*base)%mod;
		base=(base*base)%mod;
		exponent/=2;
	}
	return ans;
}
 
ll gcd(ll a, ll b){
	if(b==0) return a;
	else return gcd(b,a%b);
}
 
const int INF = 2e9;
const ll INFLL = 2e18;
const int ul = 1e6+1;
const int mod = 1e9+7;

struct treap_node{
	treap_node *l, *r;
	int pri, cnt;
	int ind;
	ll val, agg;

	treap_node(int _ind, ll _val) : ind(_ind), val(_val), pri(rand()), l(nullptr), r(nullptr), agg(_val) {}

	// void push() {}

	void pull(){
		agg = val;
		if(l != nullptr) agg = gcd(agg,l->agg);
		if(r != nullptr) agg = gcd(agg,r->agg);
	}
};

void split(treap_node *root, int ind, ll val, treap_node *&l, treap_node *&r){
	if(root == nullptr){
		l = r = nullptr;
		return;
	}

	// root->push();
	bool cmp;
	if(root->ind == ind) cmp = (val >= root->val);
	else cmp = (ind >= root->ind);

	if(cmp) split(root->r, ind, val, l, r), root->r = l, l = root;
	else split(root->l, ind, val, l, r), root->l = r, r = root;
	root->pull();
}

treap_node *merge(treap_node *root_l, treap_node *root_r){
	if(root_l == nullptr) return root_r;
	if(root_r == nullptr) return root_l;

	// root_l->push(); root_r->push();

	if(root_l->pri >= root_r->pri){
		root_l->r = merge(root_l->r, root_r);
		root_l->pull();
		return root_l;
	}
	else{
		root_r->l = merge(root_l, root_r->l);
		root_r->pull();
		return root_r;
	}
}

treap_node *delete_rightmost_node(treap_node *node){
	if(node == nullptr) return nullptr;
	if(node->r == nullptr){
		treap_node *ans = node->l;
		delete node;
		return ans;
	}
	else{
		node->r = delete_rightmost_node(node->r);
		node->pull();
		return node;
	}
}

void delete_in_treap(treap_node *&root, int ind, ll val){
	if(! val) return;
	treap_node *l = nullptr, *r = nullptr;
	split(root,ind,val,l,r);

	l = delete_rightmost_node(l);

	root = merge(l,r);
}

void insert_in_treap(treap_node *&root, int ind, ll val){
	if(! val) return;
	treap_node *l = nullptr, *r = nullptr;
	split(root,ind,val,l,r);

	treap_node *nw = new treap_node(ind,val);
	l = merge(l,nw);
	root = merge(l,r);
}

ll query_treap(treap_node *&root, int l, int r){
	treap_node *a = nullptr, *b = nullptr, *c = nullptr;
	split(root,r+1,0,b,c);
	split(b,l,0,a,b);
	ll ans = (b ? b->agg : 0);
	b = merge(a,b);
	root = merge(b,c);
	return ans;
}

struct seg_node{
	seg_node *l, *r;
	treap_node *treap;
	seg_node(){
		l = r = nullptr;
		treap = nullptr;
	}
};

void update_segtree(seg_node *&node, int i, int j, int x, int y, ll val, ll prev_val){
	if(node == nullptr) node = new seg_node();
	delete_in_treap(node->treap, y, prev_val);
	insert_in_treap(node->treap, y, val);
	if(i == j) return;
	int mid = (i + j) >> 1;
	if(x <= mid) update_segtree(node->l, i, mid, x, y, val, prev_val);
	else update_segtree(node->r, mid+1, j, x, y, val, prev_val);
}

ll query_segtree(seg_node *node, int i, int j, int x1, int y1, int x2, int y2){
	if(node == nullptr || i > x2 || x1 > j || i > j || x1 > x2) return 0;
	if(i >= x1 && j <= x2) return query_treap(node->treap, y1, y2);
	int mid = (i + j) >> 1;
	return gcd(query_segtree(node->l,i,mid,x1,y1,x2,y2), query_segtree(node->r,mid+1,j,x1,y1,x2,y2));
}

int R,C;
map<int,map<int,ll>> grid;
seg_node *segtree;

void init(int _R, int _C){
	srand(time(NULL));
	R = _R;
	C = _C;
}

void update(int P, int Q, long long x){
	// cout << P << " " << Q << " " << grid[P][Q] << "\n";
	update_segtree(segtree, 0, R - 1, P, Q, x, grid[P][Q]);
	grid[P][Q] = x;
}

long long calculate(int P, int Q, int U, int V){
	if(P > U) swap(P,U);
	if(Q > V) swap(Q,V);
	return query_segtree(segtree, 0, R - 1, P, Q, U, V);
}

void solve(){
	int n,m,q,typ,l1,r1,l2,r2;
	ll val;
	cin >> n >> m >> q;
	init(n,m);
	while(q--){
		cin >> typ;
		if(typ == 1) cin >> l1 >> r1 >> val, update(l1,r1,val);
		else cin >> l1 >> r1 >> l2 >> r2, cout << calculate(l1,r1,l2,r2) << "\n";
	}
}
 
// signed main(){
// 	ios::sync_with_stdio(0);
// 	cin.tie(0); cout.tie(0);
 
// 	srand(time(NULL));
// 	int t = 1;
// 	// cin >> t;
// 	while(t--) solve();
// 	return 0;
// }

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