oj.uz

Submission #52147

# Submission time Handle Problem Language Result Execution time Memory
52147 2018-06-24T09:19:01 Z gnoor Game (IOI13_game) C++17
10 / 100
 13000 ms 55996 KB 
#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};
}

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) {
		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");
				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;
	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));
		}
	}
	return gcd;
}

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 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 3 ms 432 KB Output is correct
4 Correct 3 ms 672 KB Output is correct
5 Correct 2 ms 672 KB Output is correct
6 Correct 4 ms 672 KB Output is correct
7 Correct 3 ms 672 KB Output is correct
8 Correct 3 ms 672 KB Output is correct
9 Correct 2 ms 672 KB Output is correct
10 Correct 2 ms 672 KB Output is correct
11 Correct 2 ms 676 KB Output is correct
12 Correct 2 ms 676 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 692 KB Output is correct
2 Correct 2 ms 692 KB Output is correct
3 Correct 2 ms 692 KB Output is correct
4 Correct 2863 ms 10728 KB Output is correct
5 Correct 383 ms 14804 KB Output is correct
6 Correct 9459 ms 16468 KB Output is correct
7 Execution timed out 13096 ms 19624 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 19624 KB Output is correct
2 Correct 3 ms 19624 KB Output is correct
3 Correct 3 ms 19624 KB Output is correct
4 Correct 2 ms 19624 KB Output is correct
5 Correct 2 ms 19624 KB Output is correct
6 Correct 3 ms 19624 KB Output is correct
7 Correct 2 ms 19624 KB Output is correct
8 Correct 2 ms 19624 KB Output is correct
9 Correct 3 ms 19624 KB Output is correct
10 Correct 2 ms 19624 KB Output is correct
11 Correct 3 ms 19624 KB Output is correct
12 Execution timed out 13011 ms 25456 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25456 KB Output is correct
2 Correct 3 ms 25456 KB Output is correct
3 Correct 3 ms 25456 KB Output is correct
4 Correct 2 ms 25456 KB Output is correct
5 Correct 2 ms 25456 KB Output is correct
6 Correct 2 ms 25456 KB Output is correct
7 Correct 2 ms 25456 KB Output is correct
8 Correct 2 ms 25456 KB Output is correct
9 Correct 3 ms 25456 KB Output is correct
10 Correct 3 ms 25456 KB Output is correct
11 Correct 3 ms 25456 KB Output is correct
12 Correct 2729 ms 30972 KB Output is correct
13 Correct 415 ms 34936 KB Output is correct
14 Correct 9373 ms 36504 KB Output is correct
15 Execution timed out 13059 ms 39412 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 39412 KB Output is correct
2 Correct 2 ms 39412 KB Output is correct
3 Correct 3 ms 39412 KB Output is correct
4 Correct 2 ms 39412 KB Output is correct
5 Correct 3 ms 39412 KB Output is correct
6 Correct 3 ms 39412 KB Output is correct
7 Correct 3 ms 39412 KB Output is correct
8 Correct 2 ms 39412 KB Output is correct
9 Correct 2 ms 39412 KB Output is correct
10 Correct 3 ms 39412 KB Output is correct
11 Correct 2 ms 39412 KB Output is correct
12 Correct 2770 ms 47312 KB Output is correct
13 Correct 377 ms 51516 KB Output is correct
14 Correct 9539 ms 53144 KB Output is correct
15 Execution timed out 13063 ms 55996 KB Time limit exceeded
16 Halted 0 ms 0 KB -