oj.uz

Submission #141707

# Submission time Handle Problem Language Result Execution time Memory
141707 2019-08-09T00:01:48 Z liwi Game (IOI13_game) C++11
80 / 100
 13000 ms 69124 KB 
#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);}

	bool contains(node<T> *&n, int col){
		if(!n) return false;
		if(n->val.first == col) return true;
		return contains(n->val.first<col?n->r:n->l,col);
	}
	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(rt,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);
		}
		upd(rt);
	}
	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 push_up(int col){
		ll gg = __gcd(lft?lft->s.range_query(col,col):0,rgt?rgt->s.range_query(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(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;
map<pii,ll> m;
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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 4 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 2 ms 376 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2216 ms 7216 KB Output is correct
5 Correct 988 ms 7416 KB Output is correct
6 Correct 2847 ms 4284 KB Output is correct
7 Correct 3431 ms 4000 KB Output is correct
8 Correct 2189 ms 3368 KB Output is correct
9 Correct 3262 ms 4008 KB Output is correct
10 Correct 2884 ms 3680 KB Output is correct
11 Correct 2 ms 376 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 4 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 4 ms 380 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3543 ms 11468 KB Output is correct
13 Correct 7711 ms 8176 KB Output is correct
14 Correct 955 ms 8484 KB Output is correct
15 Correct 8762 ms 13148 KB Output is correct
16 Correct 1113 ms 13112 KB Output is correct
17 Correct 4824 ms 9884 KB Output is correct
18 Correct 8667 ms 13400 KB Output is correct
19 Correct 7359 ms 13572 KB Output is correct
20 Correct 7314 ms 12984 KB Output is correct
21 Correct 2 ms 376 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 4 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 2202 ms 7288 KB Output is correct
13 Correct 965 ms 7516 KB Output is correct
14 Correct 2907 ms 4160 KB Output is correct
15 Correct 3433 ms 4080 KB Output is correct
16 Correct 2153 ms 3456 KB Output is correct
17 Correct 3220 ms 4256 KB Output is correct
18 Correct 2771 ms 3868 KB Output is correct
19 Correct 3414 ms 11536 KB Output is correct
20 Correct 8061 ms 8300 KB Output is correct
21 Correct 953 ms 8504 KB Output is correct
22 Correct 8544 ms 13136 KB Output is correct
23 Correct 1094 ms 13124 KB Output is correct
24 Correct 4805 ms 9680 KB Output is correct
25 Correct 8703 ms 13480 KB Output is correct
26 Correct 7292 ms 13544 KB Output is correct
27 Correct 7265 ms 13020 KB Output is correct
28 Correct 2574 ms 30924 KB Output is correct
29 Correct 4738 ms 34148 KB Output is correct
30 Correct 10414 ms 29224 KB Output is correct
31 Correct 9383 ms 28260 KB Output is correct
32 Correct 1257 ms 23644 KB Output is correct
33 Correct 2163 ms 23720 KB Output is correct
34 Correct 1456 ms 32996 KB Output is correct
35 Correct 5462 ms 18348 KB Output is correct
36 Correct 10263 ms 35332 KB Output is correct
37 Correct 8399 ms 35392 KB Output is correct
38 Correct 8986 ms 34792 KB Output is correct
39 Correct 6927 ms 27040 KB Output is correct
40 Correct 2 ms 376 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 7 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 2261 ms 7176 KB Output is correct
13 Correct 1002 ms 7560 KB Output is correct
14 Correct 2967 ms 4472 KB Output is correct
15 Correct 3454 ms 4016 KB Output is correct
16 Correct 2139 ms 3428 KB Output is correct
17 Correct 3176 ms 4248 KB Output is correct
18 Correct 2804 ms 3752 KB Output is correct
19 Correct 3363 ms 11508 KB Output is correct
20 Correct 7785 ms 8276 KB Output is correct
21 Correct 1008 ms 8520 KB Output is correct
22 Correct 8842 ms 13120 KB Output is correct
23 Correct 1128 ms 13000 KB Output is correct
24 Correct 4839 ms 9832 KB Output is correct
25 Correct 8636 ms 13540 KB Output is correct
26 Correct 7477 ms 13584 KB Output is correct
27 Correct 7299 ms 12796 KB Output is correct
28 Correct 2605 ms 36264 KB Output is correct
29 Correct 4754 ms 39148 KB Output is correct
30 Correct 10712 ms 28452 KB Output is correct
31 Correct 9550 ms 27628 KB Output is correct
32 Correct 1255 ms 27172 KB Output is correct
33 Correct 2215 ms 27156 KB Output is correct
34 Correct 1463 ms 32224 KB Output is correct
35 Correct 5502 ms 22372 KB Output is correct
36 Correct 9992 ms 35900 KB Output is correct
37 Correct 8340 ms 35808 KB Output is correct
38 Correct 8779 ms 35376 KB Output is correct
39 Correct 3509 ms 67064 KB Output is correct
40 Correct 8186 ms 69124 KB Output is correct
41 Execution timed out 13080 ms 54820 KB Time limit exceeded
42 Halted 0 ms 0 KB -