oj.uz

Submission #141704

# Submission time Handle Problem Language Result Execution time Memory
141704 2019-08-08T23:14:43 Z liwi Game (IOI13_game) C++11
37 / 100
 9610 ms 13952 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 replace(node<T> *&n, int idx, ll old_v, ll v){
		if(!n) return;
		if(n->val == mp(idx,old_v)){
			n->val.second = v;
			node<T> *rr=0,*l=0,*r=0;
			split(n,n->val,l,r);
			merge(rr,l,r);
		}else replace(n->val<mp(idx,old_v)?n->r:n->l,idx,old_v,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, ll ov){
		if(ins) s.insert(s.rt,new node<pair<int,ll>>(mp(col,val)));
		else s.replace(s.rt,col,ov,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,ov);
		}else{
			if(!rgt) rgt = new snode(mid+1,r);
			rgt->update(row,col,val,ins,ov);
		}
	}
	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++;
	ull e = m.count(mp(P,Q));
	seg->update(P,Q,K,!e,e?m[mp(P,Q)]:0);
	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 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 2 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 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 256 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 2063 ms 8664 KB Output is correct
5 Correct 757 ms 9068 KB Output is correct
6 Correct 2544 ms 6640 KB Output is correct
7 Correct 3053 ms 6396 KB Output is correct
8 Correct 2017 ms 4876 KB Output is correct
9 Correct 2854 ms 6568 KB Output is correct
10 Correct 2475 ms 6092 KB Output is correct
11 Correct 2 ms 256 KB Output is correct

Subtask #3
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 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 3 ms 380 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 3213 ms 12968 KB Output is correct
13 Correct 9302 ms 7564 KB Output is correct
14 Incorrect 1197 ms 2940 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.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 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 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 1986 ms 9176 KB Output is correct
13 Correct 843 ms 9052 KB Output is correct
14 Correct 2565 ms 6644 KB Output is correct
15 Correct 3081 ms 6352 KB Output is correct
16 Correct 2017 ms 4960 KB Output is correct
17 Correct 2884 ms 6520 KB Output is correct
18 Correct 2571 ms 6264 KB Output is correct
19 Correct 3265 ms 13952 KB Output is correct
20 Correct 9327 ms 8272 KB Output is correct
21 Incorrect 1187 ms 2708 KB Output isn't correct
22 Halted 0 ms 0 KB -

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 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 404 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 2041 ms 8756 KB Output is correct
13 Correct 867 ms 8952 KB Output is correct
14 Correct 2529 ms 6392 KB Output is correct
15 Correct 3037 ms 6028 KB Output is correct
16 Correct 2000 ms 4552 KB Output is correct
17 Correct 2852 ms 6200 KB Output is correct
18 Correct 2487 ms 6228 KB Output is correct
19 Correct 3326 ms 13892 KB Output is correct
20 Correct 9610 ms 8180 KB Output is correct
21 Incorrect 1264 ms 2680 KB Output isn't correct
22 Halted 0 ms 0 KB -