Submission #141697

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
141697	2019-08-08T22:31:25 Z	liwi	Game (IOI13_game)	C++11	0 / 100	9296 ms	16092 KB

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; int sz; ll prior,gg;
	node *l,*r;
	node(T v){
		val = v, sz = 1, gg = val.second;
		prior = randlong(1,1e18);
		l = r = 0;
	}
};
 
template<typename T>
struct SMTreap{
	node<T> *rt=0;
 
	inline int gsz(node<T> *&n){return n?n->sz:0;}
	inline void upd_sz(node<T> *&n){if(n)n->sz=gsz(n->l)+gsz(n->r)+1;}
	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){upd_sz(n);upd_gcd(n);}
 
	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 insert(node<T> *&n, node<T> *v){
		if(!n) n = v;
		else if(v->prior > n->prior) split(n,v->val,v->l,v->r), n = v;
		else insert(v->val<n->val?n->l:n->r,v);
		upd(n);
	}
	void replace(node<T> *&n, int idx, ll v){
		if(!n) return;
		if(n->val.first == idx) n->val.second = v;
		else replace(n->val.first<idx?n->r:n->l,idx,v);
		upd(n);
	}
	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(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;
	}
	void print(){
		for(int i=1; i<=gsz(rt); i++)
			printf("%d ",find_by_order(rt,i));
		printf("\n");
	}
};
 
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 update(int row, int col, ll val, int ins){
		if(ins) s.insert(s.rt,new node<pair<int,ll>>(mp(col,val)));
		else s.replace(s.rt,col,val);
		if(l == r) return;
		int mid = (l+r)/2;
		if(row <= mid){
			if(!lft) lft = new snode(l,mid);
			lft->update(row,col,val,ins);
		}else{
			if(!rgt) rgt = new snode(mid+1,r);
			rgt->update(row,col,val,ins);
		}
	}
	ll query(int rl, int rr, int cl, int cr){
		if(l == rl && r == rr) return s.range_query(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;
set<pii> s;
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,!s.count(mp(P,Q)));
	s.insert(mp(P,Q));
}
 
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

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

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct
3	Correct	3 ms	376 KB	Output is correct
4	Incorrect	2 ms	376 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #2

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	380 KB	Output is correct
2	Incorrect	2 ms	256 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3

0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	380 KB	Output is correct
3	Correct	3 ms	376 KB	Output is correct
4	Incorrect	2 ms	296 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #4

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	3 ms	380 KB	Output is correct
3	Correct	3 ms	376 KB	Output is correct
4	Correct	2 ms	256 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	3 ms	376 KB	Output is correct
7	Correct	2 ms	256 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	3 ms	452 KB	Output is correct
10	Correct	3 ms	376 KB	Output is correct
11	Correct	3 ms	376 KB	Output is correct
12	Correct	1967 ms	8316 KB	Output is correct
13	Correct	842 ms	8868 KB	Output is correct
14	Correct	2626 ms	5240 KB	Output is correct
15	Correct	3163 ms	5020 KB	Output is correct
16	Correct	2039 ms	4476 KB	Output is correct
17	Correct	2976 ms	5244 KB	Output is correct
18	Correct	2670 ms	8916 KB	Output is correct
19	Correct	3411 ms	16092 KB	Output is correct
20	Incorrect	9050 ms	10564 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct
3	Correct	3 ms	376 KB	Output is correct
4	Correct	2 ms	256 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	3 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	360 KB	Output is correct
9	Correct	3 ms	376 KB	Output is correct
10	Correct	3 ms	376 KB	Output is correct
11	Correct	3 ms	376 KB	Output is correct
12	Correct	1894 ms	8708 KB	Output is correct
13	Correct	792 ms	9144 KB	Output is correct
14	Correct	2685 ms	5808 KB	Output is correct
15	Correct	3060 ms	5460 KB	Output is correct
16	Correct	2053 ms	4812 KB	Output is correct
17	Correct	2934 ms	5496 KB	Output is correct
18	Correct	2553 ms	8688 KB	Output is correct
19	Correct	3331 ms	15976 KB	Output is correct
20	Incorrect	9296 ms	10460 KB	Output isn't correct
21	Halted	0 ms	0 KB	-