oj.uz

Submission #141686

# Submission time Handle Problem Language Result Execution time Memory
141686 2019-08-08T21:53:20 Z liwi Game (IOI13_game) C++11
80 / 100
 13000 ms 74808 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 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 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 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 504 KB Output is correct
4 Correct 1988 ms 12204 KB Output is correct
5 Correct 847 ms 12028 KB Output is correct
6 Correct 2578 ms 9480 KB Output is correct
7 Correct 3119 ms 9340 KB Output is correct
8 Correct 2032 ms 7788 KB Output is correct
9 Correct 2895 ms 9408 KB Output is correct
10 Correct 2483 ms 9064 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 3 ms 376 KB Output is correct
3 Correct 3 ms 632 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 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 3346 ms 16352 KB Output is correct
13 Correct 9157 ms 12496 KB Output is correct
14 Correct 1365 ms 13276 KB Output is correct
15 Correct 10106 ms 13700 KB Output is correct
16 Correct 658 ms 13676 KB Output is correct
17 Correct 4534 ms 10656 KB Output is correct
18 Correct 8048 ms 15188 KB Output is correct
19 Correct 6603 ms 15252 KB Output is correct
20 Correct 6696 ms 14724 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 4 ms 376 KB Output is correct
3 Correct 4 ms 504 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 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 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 1966 ms 12276 KB Output is correct
13 Correct 866 ms 12156 KB Output is correct
14 Correct 2575 ms 9520 KB Output is correct
15 Correct 2988 ms 9336 KB Output is correct
16 Correct 1982 ms 7928 KB Output is correct
17 Correct 2862 ms 9576 KB Output is correct
18 Correct 2483 ms 9208 KB Output is correct
19 Correct 3143 ms 16248 KB Output is correct
20 Correct 9031 ms 12620 KB Output is correct
21 Correct 1347 ms 13064 KB Output is correct
22 Correct 9934 ms 13704 KB Output is correct
23 Correct 667 ms 13564 KB Output is correct
24 Correct 4500 ms 10688 KB Output is correct
25 Correct 8192 ms 15280 KB Output is correct
26 Correct 6705 ms 15352 KB Output is correct
27 Correct 6762 ms 14696 KB Output is correct
28 Correct 2282 ms 39824 KB Output is correct
29 Correct 4375 ms 42472 KB Output is correct
30 Correct 11877 ms 32532 KB Output is correct
31 Correct 10704 ms 31516 KB Output is correct
32 Correct 1829 ms 29528 KB Output is correct
33 Correct 2890 ms 29604 KB Output is correct
34 Correct 910 ms 36248 KB Output is correct
35 Correct 5087 ms 25700 KB Output is correct
36 Correct 9378 ms 40404 KB Output is correct
37 Correct 7359 ms 40604 KB Output is correct
38 Correct 7910 ms 39872 KB Output is correct
39 Correct 6487 ms 33628 KB Output is correct
40 Correct 2 ms 252 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 504 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 376 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 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2033 ms 12400 KB Output is correct
13 Correct 833 ms 12024 KB Output is correct
14 Correct 2548 ms 9492 KB Output is correct
15 Correct 3058 ms 9332 KB Output is correct
16 Correct 2017 ms 8120 KB Output is correct
17 Correct 2848 ms 9376 KB Output is correct
18 Correct 2473 ms 9164 KB Output is correct
19 Correct 3346 ms 16280 KB Output is correct
20 Correct 9364 ms 12600 KB Output is correct
21 Correct 1368 ms 13140 KB Output is correct
22 Correct 10151 ms 13788 KB Output is correct
23 Correct 815 ms 13732 KB Output is correct
24 Correct 4450 ms 10752 KB Output is correct
25 Correct 8007 ms 15108 KB Output is correct
26 Correct 6610 ms 15452 KB Output is correct
27 Correct 6647 ms 14728 KB Output is correct
28 Correct 2409 ms 39840 KB Output is correct
29 Correct 4315 ms 42596 KB Output is correct
30 Correct 12726 ms 32444 KB Output is correct
31 Correct 10780 ms 31552 KB Output is correct
32 Correct 1853 ms 29648 KB Output is correct
33 Correct 2857 ms 29472 KB Output is correct
34 Correct 656 ms 36100 KB Output is correct
35 Correct 5082 ms 25928 KB Output is correct
36 Correct 9248 ms 40400 KB Output is correct
37 Correct 7437 ms 40580 KB Output is correct
38 Correct 8135 ms 39936 KB Output is correct
39 Correct 2926 ms 72880 KB Output is correct
40 Correct 6805 ms 74808 KB Output is correct
41 Execution timed out 13022 ms 57288 KB Time limit exceeded
42 Halted 0 ms 0 KB -