Submission #52151

#	Time	Username	Problem	Language	Result	Execution time	Memory
52151		gnoor	Game (IOI13_game)	C++17	37 / 100	13085 ms	52936 KiB

game

#include "game.h"

#ifdef debug
#include "grader.cpp"
#endif

#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstdlib>

using namespace std;

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

pair<int,int> inv(const pair<int,int> &x) {
	return {x.second,x.first};
}


int stepcnt;

struct node {
	pair<int,int> key;	//col,row
	int prior;
	long long val;
	long long gcd;
	//pair<int,int> mn;
	//pair<int,int> mx;
	node *l, *r;

	node(pair<int,int> _key,long long _val): key(_key),prior((rand()<<16)^rand()),val(_val),gcd(_val),/*mn(_key),mx(_key),*/l(0),r(0) {}

	static void print(node *x) {
		if (!x) return;
		print(x->l);
		//printf("%d,%d:%d,%d:%lld,%lld ",x->key.second,x->key.first,x->mn.first,x->mx.first,x->val,x->gcd);
		print(x->r);
	}

	static void update(node *x) {
		if (!x) return;
		x->gcd=x->val;
		//x->mn=x->mx=x->key;
		if (x->l) {
			x->gcd=gcd2(x->gcd,x->l->gcd);
			//x->mn=min(x->mn,x->l->mn);	
		}
		if (x->r) {
			x->gcd=gcd2(x->gcd,x->r->gcd);
			//x->mx=max(x->mx,x->r->mx);
		}
	}	

	static bool change(node *x,const pair<int,int> &key,long long newval) {
		if (!x) return false;
		if (x->key==key) {
			x->val=newval;
			update(x);
			return true;
		}
		bool res=change((x->key<key)?x->r:x->l,key,newval);
		update(x);
		return res;
	}

	static void split(node *x,node* &l, node* &r,pair<int,int> key) {
		if (!x) l=r=NULL;
		else if (x->key<key) {
			l=x;
			split(x->r,x->r,r,key);
		} else {
			r=x;
			split(x->l,l,x->l,key);
		}
		update(x);
	}

	static void merge(node* &x,node *l,node *r) {
		if(!l||!r) x=(l)?l:r;
		else if (l->prior>r->prior) {
			x=l;
			merge(x->r,x->r,r);
		} else {
			x=r;
			merge(x->l,l,x->l);
		}
		update(x);
	}

	static void insert(node* &x, node *n) {
		if (!x) x=n;
		else if (n->prior>x->prior) {
			split(x,n->l,n->r,n->key);
			x=n;
		} else {
			insert((x->key<n->key)?x->r:x->l,n);
		}
		update(x);
	}

	static void erase(node* &x, pair<int,int> key) {
		if (!x) return;
		if (x->key==key) {
			merge(x,x->l,x->r);
		} else {
			erase(x->key<key?x->r:x->l,key);
		}
		update(x);
	}

	static void insertFrom(node* &dest,node* src) {
		if (!src) return;
		insert(dest,new node(src->key,src->val));
		insertFrom(dest,src->l);
		insertFrom(dest,src->r);
	}

	static void eraseFrom(node* &dest,node* src) {
		if (!src) return;
		erase(dest,src->key);
		eraseFrom(dest,src->l);
		eraseFrom(dest,src->r);
	}

	static long long query(node* &x, int lo,int hi) {
		node *l,*m,*r;
		split(x,l,m,{lo,-1});
		split(m,m,r,{hi,1e9+7});
		long long ans=(m)?m->gcd:0;
		merge(m,m,r);
		merge(x,l,m);
		return ans;
	}

	//static long long query(node *x,int lo,int hi) {
		//stepcnt++;
		//if (!x) return 0;
		//if (lo<=x->mn.first&&x->mx.first<=hi) return x->gcd;
		//long long cur=0;
		//if (x->key.first>=lo&&x->key.first<=hi) cur=x->val;
		//return gcd2(cur,gcd2(query(x->l,lo,hi),query(x->r,lo,hi)));
	//}
};

struct listnode {
	int key;
	node *val;
	listnode *prv,*nxt;

	listnode(int _key): key(_key),val(0),prv(0),nxt(0) {}

	static void insert(listnode *x,listnode *n) {
		if (x->prv) {
			x->prv->nxt=n;
		}
		n->prv=x->prv;
		n->nxt=x;
		x->prv=n;
	}	
};

listnode* last=new listnode(1e9+7);

struct cluster {
	node *big;
	listnode *fst,*lst;
	int size;
	
	cluster(listnode *init): big(0),fst(init),lst(init),size(1) {}

	listnode* find(int val) {
		//printf("%d %d %d\n",fst->key,lst->key,val);
		if (val<fst->key) return fst;
		if (val>lst->key) return NULL;
		for (listnode *it=fst;it!=lst;it=it->nxt) {
			if (it->key>=val) return it;
		}
		return lst;
	}

	long long query(int P,int Q,int U,int V) {
		long long gcd=0;
		for (listnode *it=fst;it!=lst;it=it->nxt) {
			if (it->key>=P&&it->key<=U) {
				//printf("node query %d: %d %d\n",it->key,Q,V);
				//node::print(it->val);
				//printf("\n");
				stepcnt++;
				gcd=gcd2(gcd,node::query(it->val,Q,V));
				//printf("--> %lld\n",node::query(it->val,Q,V));
			}
		}
		return gcd;
	}
};

listnode* head;
int cnt;
int blk;
vector<cluster> cls;

void init(int R, int C) {
	head=last;
	cnt=1;
	blk=1;
	cls.push_back(cluster(head));
}

void update(int P, int Q, long long K) {
	//printf("update %d %d %lld\n",P,Q,K);
	//find which cluster
	int id=-1;
	for (int i=0;i<(int)cls.size();i++) {
		if (cls[i].lst->key<P) continue;
		id=i;
		break;
	}
	//printf("id %d %d %d\n",id,cls[id].fst->key,cls[id].lst->key);
	//check if R already exists
	listnode* curR=cls[id].find(P);
	//printf("curR %d\n",curR->key);
	//printf("%x\n",curR);
	if (curR!=NULL&&curR->key==P) {
		//exists
		//printf("exists\n");
		bool res = node::change(curR->val,{Q,P},K);
		node::change(cls[id].big,{Q,P},K);
		if (!res) {
			//C does not exist
			//printf("C not exist\n");
			node::insert(curR->val,new node({Q,P},K));
			node::insert(cls[id].big,new node({Q,P},K));
		}
	} else {
		//does not exist
		//printf("not exist\n");
		listnode* newR=new listnode(P);
		listnode::insert(curR,newR);	
		if (curR==cls[id].fst) cls[id].fst=newR;	
		cls[id].size++;	
		curR=newR;
		cnt++;
		//printf("curR %d\n",curR->key);
		
		//insert C in curR
		node::insert(curR->val,new node({Q,P},K));				
		node::insert(cls[id].big,new node({Q,P},K));

		head=cls[0].fst;

		//if cnt is square, increase blk
		
		//adjust block
		//int blkCnt=(int)cls.size();
		//for (int i=id;i<blkCnt;i++) {
			//if (cls[i].size>blk) {
				////move lst to next cluster
				//node::eraseFrom(cls[i].big,cls[i].lst->val);
				//if (i==blkCnt-1) {
					//cls.push_back(cluster(cls[i].lst));
				//} else {
					//node::insertFrom(cls[i+1].big,cls[i].lst->val);	
					//cls[i+1].fst=cls[i+1].fst->prv;
					//cls[i+1].size++;
				//}
				//cls[i].lst=cls[i].lst->prv;
				//cls[i].size--;
			//}
			//break;
		//}
	}

	//for (int i=0;i<(int)cls.size();i++) {
		//printf("%d: %d,%d ",i,cls[i].fst->key,cls[i].lst->key);
		//for (listnode* it=cls[i].fst;it!=cls[i].lst;it=it->nxt) {
			//printf("%d ",it->key);
		//}
		//printf("%d\n",cls[i].lst->key);
	//}

	//for (listnode* it=head;it!=last;it=it->nxt) {
		//printf("%d ",it->key);
	//}
	//printf("\n");
}

long long calculate(int P, int Q, int U, int V) {
	//printf("ask %d %d %d %d\n",P,Q,U,V);
	long long gcd=0;
	//printf("-- %d cls\n",cls.size());
	stepcnt=0;
	for (int i=0;i<(int)cls.size();i++) {
		if (P>cls[i].lst->key||U<cls[i].fst->key) continue;
		//printf("%d %d\n",cls[i].fst->key,cls[i].lst->key);
		if (P<=cls[i].fst->key&&cls[i].lst->key<=U) {
			//printf("yay\n");
			gcd=gcd2(gcd,node::query(cls[i].big,Q,V));
		} else {
			//printf("eiei\n");
			gcd=gcd2(gcd,cls[i].query(P,Q,U,V));
		}
	}
	//printf("-- %d steps\n",stepcnt);
	return gcd;
}

Compilation message (stderr)

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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20