Submission #1191777

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191777		tyellow	Game (IOI13_game)	C++20	100 / 100	4143 ms	72516 KiB

game

#include "game.h"
#include"bits/stdc++.h"
#define pb push_back
#define ll long long
#define pii pair<ll,ll>
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)(x).size()
#define F first
#define S second
#define IOS ios::sync_with_stdio(false),cin.tie(0);
using namespace std;
const ll inf =  1000000000;
const ll maxn = 2e5;
ll r , c , n ; 
//Treap
struct node
{
	node *l , *r;
	ll pri , val , gcd , pos;
	node(){}
	node(ll _val , ll _pos){
		l=r=nullptr;
		pri = rand() , val = _val , gcd=_val , pos = _pos;
	}
	inline void up(){
		ll a = 0 , b = 0;
		if(l!=nullptr) a = l->gcd;
		if(r!=nullptr) b = r->gcd;
		gcd = __gcd(val,__gcd(a , b));
	}
}mem[maxn<<3];

node *merge(node *a , node *b){
	if(a == nullptr) return b;
	if(b == nullptr) return a;
	if(a->pri < b->pri){
		a->r = merge(a->r , b);
		return a->up() , a;
	}
	else{
		b->l = merge(a , b->l);
		return b->up() , b;
	}
}
void split(node *root , node *&a , node *&b , ll pos){
	if(root == nullptr) return a=b=nullptr , void();
	if(root->pos <= pos){
		a = root;
		split(root->r , a->r , b , pos);
	}
	else{
		b = root;
		split(root->l , a , b->l , pos);
	}
	root->up();
}
ll top = 0;
void insert(node *&root , ll val , ll pos){
	node *a=nullptr , *b=nullptr , *c=nullptr , *d=nullptr;
	split(root , a , b , pos);
	split(a , c , d , pos-1);
	if(d == nullptr) mem[top]=node(val,pos) , a = merge(c , &mem[top++]) ;
	else d->val = val , d->gcd = val , a = merge(c , d);
	root = merge(a , b);
}
ll query(node *&root , ll l , ll  r, ll x1 , ll x2){
	ll res = 0;
	node *a , *b , *c , *d;
	split(root , a , b , l-1);
	split(b , c , d , r);
	if(c != nullptr) res = c->gcd;
	root = merge(a , merge(c , d));
	return res;
}
//Segment Tree
struct st
{
	st *lc , *rc;
	node *treap;
	st(){
		lc = rc = nullptr;
		treap = nullptr;
	}
}*stroot=nullptr,stmem[maxn<<3];
ll sttop;

ll st_query(ll l , ll r , ll x1 , ll x2 , ll y1 , ll y2 , st *rt){
	if(rt == nullptr) return 0;
	if(rt->treap == nullptr) return 0;
	if(x1 <= l && r <= x2) return query(rt->treap , y1 , y2 , l , r);
	ll mid = (l+r)>>1;
	if(x2 <= mid) return st_query(l , mid , x1 , x2 , y1 , y2 , rt->lc);
	else if(x1 > mid) return st_query(mid+1 , r , x1 , x2 , y1 , y2 , rt->rc);
	else	return __gcd(st_query(l , mid , x1 , x2 , y1 , y2 , rt->lc)
						,st_query(mid+1 , r , x1 , x2 , y1 , y2 , rt->rc));
	
}
void modify(ll l , ll r , ll x , ll y , ll val , st *&rt){
	if(rt == nullptr) stmem[sttop]=st() , rt = &stmem[sttop++];
	if(l == r) return insert(rt->treap , val , y), void();
	ll mid = (l+r)>>1;
	if(x <= mid) modify(l , mid , x , y , val , rt->lc);
	else modify(mid+1 , r , x , y , val , rt->rc);
	//merge treap
	if(rt->lc == nullptr && rt->rc == nullptr) insert(rt->treap , val , y);
	else if(rt->rc == nullptr) insert(rt->treap , query(rt->lc->treap , y , y , l , r) , y);
	else if(rt->lc == nullptr) insert(rt->treap , query(rt->rc->treap , y , y , l , r) , y);
	else{
		ll a = query(rt->lc->treap , y , y , l , r) , b = query(rt->rc->treap , y , y , l , r);
		insert(rt->treap , __gcd(a , b) , y);
	}
}


void init(int R, int C) {
  r = R, c = C;
}

void update(int p, int q, ll k) {
  modify(0 , r-1 , p , q , k , stroot);
}

ll calculate(int x1, int y1, int x2, int y2) {
  return st_query(0 , r-1 , x1 , x2 , y1 , y2 , stroot);
}
// signed main(){
// 	IOS;
// 	srand(time(0));
// 	cin >> r >> c >> n ;
// 	for(ll i=1 ; i<=n  ; ++i){
// 		//LINE
// 		ll type ; cin >> type;
// 		if(type == 1){
// 			ll p , q , k ; cin >> p >> q >> k ;
// 			modify(0 , r-1 , p , q , k , stroot);
// 		}
// 		else{
// 			//endl LINE endl
// 			ll x1 , y1 , x2 , y2;
// 			cin >> x1 >> y1 >> x2 >> y2;
// 			ll ans = st_query(0 , r-1 , x1 , x2 , y1 , y2 , stroot);
// 			cout << ans << '\n';
// 			//endl LINE endl
// 		}
// 	}
// }

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20