oj.uz

Submission #141997

# Submission time Handle Problem Language Result Execution time Memory
141997 2019-08-09T02:53:26 Z liwi Game (IOI13_game) C++11
100 / 100
 5824 ms 65760 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; 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

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 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 256 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 256 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 276 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 256 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 360 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 1102 ms 9308 KB Output is correct
5 Correct 468 ms 9492 KB Output is correct
6 Correct 1132 ms 6340 KB Output is correct
7 Correct 1211 ms 6212 KB Output is correct
8 Correct 674 ms 5412 KB Output is correct
9 Correct 1196 ms 6228 KB Output is correct
10 Correct 1138 ms 5928 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 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 300 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 256 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 1687 ms 13580 KB Output is correct
13 Correct 2720 ms 10064 KB Output is correct
14 Correct 339 ms 10484 KB Output is correct
15 Correct 2833 ms 10952 KB Output is correct
16 Correct 465 ms 11000 KB Output is correct
17 Correct 1445 ms 7676 KB Output is correct
18 Correct 2876 ms 11164 KB Output is correct
19 Correct 2301 ms 11332 KB Output is correct
20 Correct 2323 ms 10676 KB Output is correct
21 Correct 2 ms 256 KB Output is correct

Subtask #4
17.0 / 17.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 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 400 KB Output is correct
8 Correct 2 ms 256 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 1128 ms 9244 KB Output is correct
13 Correct 477 ms 9492 KB Output is correct
14 Correct 1093 ms 6372 KB Output is correct
15 Correct 1291 ms 6092 KB Output is correct
16 Correct 693 ms 5624 KB Output is correct
17 Correct 1193 ms 6068 KB Output is correct
18 Correct 1139 ms 5760 KB Output is correct
19 Correct 1581 ms 13600 KB Output is correct
20 Correct 2834 ms 10160 KB Output is correct
21 Correct 339 ms 10532 KB Output is correct
22 Correct 2845 ms 10948 KB Output is correct
23 Correct 448 ms 10872 KB Output is correct
24 Correct 1445 ms 7592 KB Output is correct
25 Correct 2764 ms 11420 KB Output is correct
26 Correct 2343 ms 11392 KB Output is correct
27 Correct 2355 ms 10732 KB Output is correct
28 Correct 795 ms 31752 KB Output is correct
29 Correct 2461 ms 34876 KB Output is correct
30 Correct 3395 ms 26880 KB Output is correct
31 Correct 2878 ms 26064 KB Output is correct
32 Correct 524 ms 22464 KB Output is correct
33 Correct 755 ms 22648 KB Output is correct
34 Correct 652 ms 30904 KB Output is correct
35 Correct 1793 ms 18924 KB Output is correct
36 Correct 3729 ms 32344 KB Output is correct
37 Correct 3025 ms 32612 KB Output is correct
38 Correct 3223 ms 31952 KB Output is correct
39 Correct 2512 ms 26064 KB Output is correct
40 Correct 2 ms 400 KB Output is correct

Subtask #5
20.0 / 20.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 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 380 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 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 364 KB Output is correct
12 Correct 1139 ms 9228 KB Output is correct
13 Correct 465 ms 9544 KB Output is correct
14 Correct 1080 ms 6212 KB Output is correct
15 Correct 1219 ms 6096 KB Output is correct
16 Correct 704 ms 5448 KB Output is correct
17 Correct 1168 ms 6168 KB Output is correct
18 Correct 1124 ms 5980 KB Output is correct
19 Correct 1577 ms 13604 KB Output is correct
20 Correct 2771 ms 10152 KB Output is correct
21 Correct 336 ms 10360 KB Output is correct
22 Correct 2750 ms 10868 KB Output is correct
23 Correct 471 ms 10884 KB Output is correct
24 Correct 1449 ms 7676 KB Output is correct
25 Correct 2756 ms 11288 KB Output is correct
26 Correct 2337 ms 11384 KB Output is correct
27 Correct 2297 ms 10684 KB Output is correct
28 Correct 783 ms 31864 KB Output is correct
29 Correct 2530 ms 34980 KB Output is correct
30 Correct 3327 ms 26964 KB Output is correct
31 Correct 2986 ms 26004 KB Output is correct
32 Correct 515 ms 23432 KB Output is correct
33 Correct 751 ms 23472 KB Output is correct
34 Correct 653 ms 30872 KB Output is correct
35 Correct 1841 ms 18776 KB Output is correct
36 Correct 3818 ms 32368 KB Output is correct
37 Correct 3032 ms 32552 KB Output is correct
38 Correct 3287 ms 31860 KB Output is correct
39 Correct 1203 ms 63648 KB Output is correct
40 Correct 4441 ms 65760 KB Output is correct
41 Correct 5395 ms 55292 KB Output is correct
42 Correct 4703 ms 51840 KB Output is correct
43 Correct 1645 ms 62172 KB Output is correct
44 Correct 821 ms 44440 KB Output is correct
45 Correct 2452 ms 23748 KB Output is correct
46 Correct 5824 ms 62044 KB Output is correct
47 Correct 5449 ms 61928 KB Output is correct
48 Correct 5531 ms 62088 KB Output is correct
49 Correct 2 ms 256 KB Output is correct