oj.uz

Submission #141712

# Submission time Handle Problem Language Result Execution time Memory
141712 2019-08-09T00:33:24 Z liwi Game (IOI13_game) C++11
80 / 100
 13000 ms 67636 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; ll prior,gg;
	node *l,*r;
	node(T v){
		val = v, gg = val.second;
		prior = randlong(1,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){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);
		}
		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;
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 3 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 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2205 ms 11584 KB Output is correct
5 Correct 938 ms 11300 KB Output is correct
6 Correct 2917 ms 8820 KB Output is correct
7 Correct 3252 ms 8732 KB Output is correct
8 Correct 2158 ms 7500 KB Output is correct
9 Correct 3194 ms 8656 KB Output is correct
10 Correct 2845 ms 8484 KB Output is correct
11 Correct 2 ms 256 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 5 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 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 4 ms 376 KB Output is correct
12 Correct 3450 ms 15380 KB Output is correct
13 Correct 7445 ms 12032 KB Output is correct
14 Correct 971 ms 13200 KB Output is correct
15 Correct 8555 ms 13208 KB Output is correct
16 Correct 1122 ms 13056 KB Output is correct
17 Correct 4816 ms 10368 KB Output is correct
18 Correct 8876 ms 14500 KB Output is correct
19 Correct 7481 ms 14676 KB Output is correct
20 Correct 7292 ms 14120 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 256 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 360 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 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 2200 ms 11584 KB Output is correct
13 Correct 904 ms 11444 KB Output is correct
14 Correct 3019 ms 8952 KB Output is correct
15 Correct 3367 ms 8612 KB Output is correct
16 Correct 2157 ms 7604 KB Output is correct
17 Correct 3223 ms 8708 KB Output is correct
18 Correct 2853 ms 8324 KB Output is correct
19 Correct 3375 ms 15596 KB Output is correct
20 Correct 7846 ms 12324 KB Output is correct
21 Correct 936 ms 13176 KB Output is correct
22 Correct 8611 ms 13200 KB Output is correct
23 Correct 1101 ms 12936 KB Output is correct
24 Correct 4829 ms 10256 KB Output is correct
25 Correct 8740 ms 14372 KB Output is correct
26 Correct 7346 ms 14528 KB Output is correct
27 Correct 7410 ms 14012 KB Output is correct
28 Correct 2615 ms 34116 KB Output is correct
29 Correct 4540 ms 36980 KB Output is correct
30 Correct 10344 ms 31968 KB Output is correct
31 Correct 9079 ms 31012 KB Output is correct
32 Correct 1215 ms 26468 KB Output is correct
33 Correct 2116 ms 26652 KB Output is correct
34 Correct 1400 ms 35680 KB Output is correct
35 Correct 5384 ms 20468 KB Output is correct
36 Correct 10092 ms 34184 KB Output is correct
37 Correct 8277 ms 34220 KB Output is correct
38 Correct 8733 ms 33552 KB Output is correct
39 Correct 7067 ms 27480 KB Output is correct
40 Correct 2 ms 256 KB Output is correct

Subtask #5
0 / 20.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 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 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 2104 ms 11692 KB Output is correct
13 Correct 926 ms 11332 KB Output is correct
14 Correct 2926 ms 8960 KB Output is correct
15 Correct 3328 ms 8560 KB Output is correct
16 Correct 2198 ms 7496 KB Output is correct
17 Correct 3244 ms 8760 KB Output is correct
18 Correct 2808 ms 8412 KB Output is correct
19 Correct 3273 ms 15464 KB Output is correct
20 Correct 7716 ms 12096 KB Output is correct
21 Correct 909 ms 13128 KB Output is correct
22 Correct 8775 ms 13452 KB Output is correct
23 Correct 1063 ms 13180 KB Output is correct
24 Correct 4957 ms 10356 KB Output is correct
25 Correct 8924 ms 14656 KB Output is correct
26 Correct 7401 ms 14620 KB Output is correct
27 Correct 7597 ms 14032 KB Output is correct
28 Correct 2613 ms 34332 KB Output is correct
29 Correct 4716 ms 37132 KB Output is correct
30 Correct 10398 ms 31524 KB Output is correct
31 Correct 9607 ms 30796 KB Output is correct
32 Correct 1235 ms 26104 KB Output is correct
33 Correct 2125 ms 25764 KB Output is correct
34 Correct 1332 ms 34760 KB Output is correct
35 Correct 5411 ms 20856 KB Output is correct
36 Correct 10239 ms 34324 KB Output is correct
37 Correct 8114 ms 34388 KB Output is correct
38 Correct 8659 ms 33784 KB Output is correct
39 Correct 3621 ms 65280 KB Output is correct
40 Correct 7798 ms 67636 KB Output is correct
41 Execution timed out 13057 ms 56584 KB Time limit exceeded
42 Halted 0 ms 0 KB -