oj.uz

Submission #141699

# Submission time Handle Problem Language Result Execution time Memory
141699 2019-08-08T22:35:31 Z liwi Game (IOI13_game) C++11
80 / 100
 13000 ms 69520 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);}
 
	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 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.erase(s.rt,mp(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;
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++;
	if(m.count(mp(P,Q))){
		ll s = m[mp(P,Q)];
		seg->update(P,Q,s,0);
	}
	seg->update(P,Q,K,1);
	m[mp(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 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 0 ms 256 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 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 376 KB Output is correct
4 Correct 2130 ms 9312 KB Output is correct
5 Correct 846 ms 9256 KB Output is correct
6 Correct 2629 ms 5968 KB Output is correct
7 Correct 3078 ms 5524 KB Output is correct
8 Correct 2001 ms 4876 KB Output is correct
9 Correct 2869 ms 5624 KB Output is correct
10 Correct 2551 ms 5292 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 256 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 2 ms 424 KB Output is correct
5 Correct 2 ms 380 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 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3295 ms 13628 KB Output is correct
13 Correct 9220 ms 10124 KB Output is correct
14 Correct 1376 ms 13180 KB Output is correct
15 Correct 9801 ms 13788 KB Output is correct
16 Correct 656 ms 13736 KB Output is correct
17 Correct 4576 ms 10796 KB Output is correct
18 Correct 8401 ms 15264 KB Output is correct
19 Correct 7205 ms 15352 KB Output is correct
20 Correct 6885 ms 14852 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 364 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 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 248 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 2246 ms 8484 KB Output is correct
13 Correct 823 ms 8624 KB Output is correct
14 Correct 2573 ms 5580 KB Output is correct
15 Correct 3032 ms 5260 KB Output is correct
16 Correct 2016 ms 4312 KB Output is correct
17 Correct 2854 ms 5316 KB Output is correct
18 Correct 2541 ms 4828 KB Output is correct
19 Correct 3230 ms 12456 KB Output is correct
20 Correct 9109 ms 8968 KB Output is correct
21 Correct 1339 ms 13048 KB Output is correct
22 Correct 9911 ms 13684 KB Output is correct
23 Correct 515 ms 13560 KB Output is correct
24 Correct 4558 ms 10712 KB Output is correct
25 Correct 8400 ms 15276 KB Output is correct
26 Correct 6956 ms 15164 KB Output is correct
27 Correct 6843 ms 14776 KB Output is correct
28 Correct 2330 ms 39904 KB Output is correct
29 Correct 4373 ms 42564 KB Output is correct
30 Correct 12350 ms 32676 KB Output is correct
31 Correct 10781 ms 31492 KB Output is correct
32 Correct 1821 ms 29736 KB Output is correct
33 Correct 2887 ms 29816 KB Output is correct
34 Correct 708 ms 36080 KB Output is correct
35 Correct 4946 ms 25800 KB Output is correct
36 Correct 9263 ms 38248 KB Output is correct
37 Correct 7498 ms 38468 KB Output is correct
38 Correct 7701 ms 37948 KB Output is correct
39 Correct 6249 ms 32532 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 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 376 KB Output is correct
6 Correct 2 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 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2029 ms 8340 KB Output is correct
13 Correct 848 ms 8740 KB Output is correct
14 Correct 2554 ms 5688 KB Output is correct
15 Correct 3058 ms 5312 KB Output is correct
16 Correct 1995 ms 4228 KB Output is correct
17 Correct 2885 ms 5448 KB Output is correct
18 Correct 2507 ms 4712 KB Output is correct
19 Correct 3359 ms 12520 KB Output is correct
20 Correct 9323 ms 9140 KB Output is correct
21 Correct 1350 ms 13052 KB Output is correct
22 Correct 10279 ms 13696 KB Output is correct
23 Correct 519 ms 13704 KB Output is correct
24 Correct 4644 ms 10736 KB Output is correct
25 Correct 8048 ms 15092 KB Output is correct
26 Correct 6701 ms 15216 KB Output is correct
27 Correct 6745 ms 14836 KB Output is correct
28 Correct 2312 ms 34016 KB Output is correct
29 Correct 4227 ms 37616 KB Output is correct
30 Correct 12468 ms 32612 KB Output is correct
31 Correct 10622 ms 31576 KB Output is correct
32 Correct 1816 ms 26484 KB Output is correct
33 Correct 2966 ms 26704 KB Output is correct
34 Correct 699 ms 36108 KB Output is correct
35 Correct 5009 ms 21800 KB Output is correct
36 Correct 9646 ms 35328 KB Output is correct
37 Correct 7419 ms 35492 KB Output is correct
38 Correct 8021 ms 34876 KB Output is correct
39 Correct 3035 ms 67388 KB Output is correct
40 Correct 6639 ms 69520 KB Output is correct
41 Execution timed out 13026 ms 57392 KB Time limit exceeded
42 Halted 0 ms 0 KB -