oj.uz

Submission #141708

# Submission time Handle Problem Language Result Execution time Memory
141708 2019-08-09T00:10:27 Z liwi Game (IOI13_game) C++11
80 / 100
 13000 ms 73360 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(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;
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 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 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 4 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 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2260 ms 9524 KB Output is correct
5 Correct 988 ms 9656 KB Output is correct
6 Correct 2934 ms 7420 KB Output is correct
7 Correct 3232 ms 7052 KB Output is correct
8 Correct 2127 ms 5956 KB Output is correct
9 Correct 3196 ms 7244 KB Output is correct
10 Correct 2771 ms 6804 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 4 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 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 3275 ms 13776 KB Output is correct
13 Correct 8096 ms 10324 KB Output is correct
14 Correct 966 ms 12460 KB Output is correct
15 Correct 8365 ms 10620 KB Output is correct
16 Correct 1022 ms 10308 KB Output is correct
17 Correct 4761 ms 7664 KB Output is correct
18 Correct 8724 ms 11736 KB Output is correct
19 Correct 7264 ms 11964 KB Output is correct
20 Correct 7327 ms 11396 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 5 ms 376 KB Output is correct
3 Correct 5 ms 424 KB Output is correct
4 Correct 2 ms 256 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 2145 ms 10040 KB Output is correct
13 Correct 947 ms 9872 KB Output is correct
14 Correct 2897 ms 7448 KB Output is correct
15 Correct 3237 ms 7136 KB Output is correct
16 Correct 2142 ms 5900 KB Output is correct
17 Correct 3187 ms 7432 KB Output is correct
18 Correct 2784 ms 7444 KB Output is correct
19 Correct 3264 ms 14528 KB Output is correct
20 Correct 7955 ms 11900 KB Output is correct
21 Correct 976 ms 13212 KB Output is correct
22 Correct 8358 ms 13384 KB Output is correct
23 Correct 1029 ms 13176 KB Output is correct
24 Correct 4814 ms 10372 KB Output is correct
25 Correct 8706 ms 14592 KB Output is correct
26 Correct 7505 ms 14684 KB Output is correct
27 Correct 7469 ms 14108 KB Output is correct
28 Correct 2479 ms 39000 KB Output is correct
29 Correct 4612 ms 41860 KB Output is correct
30 Correct 10139 ms 32044 KB Output is correct
31 Correct 8982 ms 31024 KB Output is correct
32 Correct 1219 ms 29708 KB Output is correct
33 Correct 2112 ms 29560 KB Output is correct
34 Correct 1491 ms 35604 KB Output is correct
35 Correct 5430 ms 25400 KB Output is correct
36 Correct 10218 ms 39856 KB Output is correct
37 Correct 8414 ms 40020 KB Output is correct
38 Correct 8673 ms 39348 KB Output is correct
39 Correct 6902 ms 33260 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 256 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 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 4 ms 364 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 396 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 2174 ms 11760 KB Output is correct
13 Correct 918 ms 11512 KB Output is correct
14 Correct 2949 ms 8952 KB Output is correct
15 Correct 3239 ms 8620 KB Output is correct
16 Correct 2123 ms 7672 KB Output is correct
17 Correct 3200 ms 8800 KB Output is correct
18 Correct 2754 ms 8312 KB Output is correct
19 Correct 3369 ms 15628 KB Output is correct
20 Correct 7897 ms 12068 KB Output is correct
21 Correct 944 ms 13052 KB Output is correct
22 Correct 8521 ms 13248 KB Output is correct
23 Correct 1075 ms 12920 KB Output is correct
24 Correct 4817 ms 10360 KB Output is correct
25 Correct 8682 ms 14684 KB Output is correct
26 Correct 7214 ms 14736 KB Output is correct
27 Correct 7254 ms 14040 KB Output is correct
28 Correct 2576 ms 39124 KB Output is correct
29 Correct 4907 ms 41764 KB Output is correct
30 Correct 10169 ms 31736 KB Output is correct
31 Correct 9077 ms 31108 KB Output is correct
32 Correct 1263 ms 29436 KB Output is correct
33 Correct 2156 ms 29568 KB Output is correct
34 Correct 1483 ms 35588 KB Output is correct
35 Correct 5436 ms 25392 KB Output is correct
36 Correct 10319 ms 39932 KB Output is correct
37 Correct 8388 ms 40056 KB Output is correct
38 Correct 8826 ms 39496 KB Output is correct
39 Correct 3636 ms 71420 KB Output is correct
40 Correct 7924 ms 73360 KB Output is correct
41 Execution timed out 13037 ms 57412 KB Time limit exceeded
42 Halted 0 ms 0 KB -