Submission #141997

#	Time	Username	Problem	Language	Result	Execution time	Memory
141997		liwi	Game (IOI13_game)	C++11	100 / 100	5824 ms	65760 KiB

game

#include "game.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;

#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;
#define complete_unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define all(a) a.begin(),a.end()
#define println printf("\n");
#define readln(x) getline(cin,x);
#define pb push_back
#define endl "\n"
#define INT_INF 0x3f3f3f3f
#define LL_INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define mp make_pair
#define fastio cin.tie(0); cin.sync_with_stdio(0);

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef unordered_map<int,int> umii;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef pair<int,pii> triple;
typedef int8_t byte;

mt19937 g1(time(0));

int randint(int a, int b){return uniform_int_distribution<int>(a, b)(g1);}
ll randlong(ll a,ll b){return uniform_int_distribution<long long>(a, b)(g1);}

ll gcd(ll a, ll b){return b == 0 ? a : gcd(b, a % b);}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
ll fpow(ll  b, ll exp, ll mod){if(exp == 0) return 1;ll t = fpow(b,exp/2,mod);if(exp&1) return t*t%mod*b%mod;return t*t%mod;}
ll divmod(ll i, ll j, ll mod){i%=mod,j%=mod;return i*fpow(j,mod-2,mod)%mod;}

template<typename T>
struct node{
	T val; ll prior,gg; int mn,mx;
	node *l,*r;
	node(T v){
		val = v, gg = val.second, mn = mx = val.first;
		prior = randlong(-1e18,1e18);
		l = r = 0;
	}
};

template<typename T>
struct SMTreap{
	node<T> *rt=0;

	inline ll ggcd(node<T> *&n){return n?n->gg:0;}
	inline void upd_gcd(node<T> *&n){if(n)n->gg=gcd(gcd(ggcd(n->l),ggcd(n->r)),n->val.second);}
	inline void upd(node<T> *&n){
		if(!n) return;
		if(n->l) n->mn = n->l->mn;
		else n->mn = n->val.first;
		if(n->r) n->mx = n->r->mx;
		else n->mx = n->val.first;
		upd_gcd(n);
	}

	bool contains(int col){
		node<T> *n = rt;
		while(n){
			if(n->val.first == col) return true;
			n = (n->val.first<col?n->r:n->l);
		}
		return false;
	}
	void split(node<T> *n, T key, node<T> *&l, node<T> *&r){
		if(!n) l = r = 0;
		else if(key < n->val) split(n->l,key,l,n->l), r = n;
		else split(n->r,key,n->r,r), l = n;
		upd(n);
	}
	void merge(node<T> *&n, node<T> *l, node<T> *r){
		if(!l || !r) n = l?l:r;
		else if(l->prior > r->prior) merge(l->r,l->r,r), n = l;
		else merge(r->l,l,r->l), n = r;
		upd(n);
	}
	void replace(node<T> *&n, int col, ll v){
		if(n->val.first == col) n->val.second = v;
		else replace(n->val.first<col?n->r:n->l,col,v);
		upd(n);
	}
	void insert(node<T> *v){
		if(contains(v->val.first)) replace(rt,v->val.first,v->val.second);
		else{
			node<T> *t1=0,*t2=0;
			split(rt,v->val,t1,t2);
			merge(t1,t1,v);
			merge(rt,t1,t2);
		}
	}
	void erase(node<T> *&n, T v){
		if(!n) return;
		if(n->val == v) merge(n,n->l,n->r);
		else erase(v<n->val?n->l:n->r,v);
		upd(n);
	}
	T kth(node<T> *&n, int idx){
		if(gsz(n->l)+1 == idx) return n->val;
		else if(gsz(n->l) >= idx) return kth(n->l,idx);
		return kth(n->r,idx-gsz(n->l)-1);
	}
//	ll range_query(node<T> *&n, int l, int r){
//		if(!rt) return 0;
//		node<T> *t1=0,*t2=0,*t3=0;
//		split(rt,mp(l,-1),t1,t2);
//		split(t2,mp(r+1,-1),t2,t3);
//		ll ans = ggcd(t2);
//		merge(rt,t1,t2);
//		merge(rt,rt,t3);
//		return ans;
//	}
	ll range_query(node<T> *&n, int l, int r){
		if(!n) return 0;
		if(n->mx < l || n->mn > r) return 0;
		if(l <= n->mn && r >= n->mx) return n->gg;
		ll ret = (n->val.first >= l && n->val.first <= r)?n->val.second:0;
		if(n->l) ret = gcd(ret,range_query(n->l,l,r));
		if(n->r) ret = gcd(ret,range_query(n->r,l,r));
		return ret;
	}
};

struct snode{
	int l,r;
	SMTreap<pair<int,ll>> s;
	snode *lft,*rgt;
	snode(int l, int r){
		this->l = l;
		this->r = r;
		lft = rgt = 0;
	}
	void push_up(int col){
		ll gg = gcd(lft?lft->s.range_query(lft->s.rt,col,col):0,rgt?rgt->s.range_query(rgt->s.rt,col,col):0);
		s.insert(new node<pair<int,ll>>(mp(col,gg)));
	}
	void update(int row, int col, ll val){
		if(l == r){
			s.insert(new node<pair<int,ll>>(mp(col,val)));
			return;
		}
		int mid = (l+r)/2;
		if(row <= mid){
			if(!lft) lft = new snode(l,mid);
			lft->update(row,col,val);
		}else{
			if(!rgt) rgt = new snode(mid+1,r);
			rgt->update(row,col,val);
		}
		push_up(col);
	}
	ll query(int rl, int rr, int cl, int cr){
		if(l == rl && r == rr) return s.range_query(s.rt,cl,cr);
		int mid = (l+r)/2;
		if(rr <= mid){
			if(!lft) return 0;
			return lft->query(rl,rr,cl,cr);
		}else if(rl > mid){
			if(!rgt) return 0;
			return rgt->query(rl,rr,cl,cr);
		}else{
			ll f = !lft?0:lft->query(rl,mid,cl,cr);
			ll s = !rgt?0:rgt->query(mid+1,rr,cl,cr);
			return gcd(f,s);
		}
	}
};

int num_rows,num_cols;
snode *seg;

void init(int R, int C){
	num_rows = R, num_cols = C;
	seg = new snode(1,R);
}

void update(int P, int Q, ll K){
	P++, Q++;
	seg->update(P,Q,K);
}

ll calculate(int r1, int c1, int r2, int c2){
	r1++, c1++, r2++, c2++;
	return seg->query(r1,r2,c1,c2);
}

void print(){
	for(int i=1; i<=num_rows; i++){
		for(int k=1; k<=num_cols; k++)
			printf("%lld ",seg->query(i,i,k,k));
		printf("\n");
	}
	printf("\n");
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

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