oj.uz

Submission #52151

# Submission time Handle Problem Language Result Execution time Memory
52151 2018-06-24T09:57:55 Z gnoor Game (IOI13_game) C++17
37 / 100
 13000 ms 52936 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};
}


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

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 3 ms 356 KB Output is correct
3 Correct 3 ms 436 KB Output is correct
4 Correct 2 ms 508 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 2 ms 568 KB Output is correct
7 Correct 2 ms 576 KB Output is correct
8 Correct 2 ms 576 KB Output is correct
9 Correct 3 ms 576 KB Output is correct
10 Correct 3 ms 576 KB Output is correct
11 Correct 3 ms 576 KB Output is correct
12 Correct 2 ms 576 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 576 KB Output is correct
2 Correct 2 ms 576 KB Output is correct
3 Correct 2 ms 576 KB Output is correct
4 Correct 1797 ms 6040 KB Output is correct
5 Correct 653 ms 6184 KB Output is correct
6 Correct 4508 ms 6184 KB Output is correct
7 Correct 5218 ms 6184 KB Output is correct
8 Correct 3471 ms 8292 KB Output is correct
9 Correct 4686 ms 12816 KB Output is correct
10 Correct 4740 ms 17096 KB Output is correct
11 Correct 2 ms 17096 KB Output is correct

Subtask #3
0 / 26.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18396 KB Output is correct
2 Correct 3 ms 18396 KB Output is correct
3 Correct 2 ms 18396 KB Output is correct
4 Correct 2 ms 18396 KB Output is correct
5 Correct 2 ms 18396 KB Output is correct
6 Correct 3 ms 18396 KB Output is correct
7 Correct 2 ms 18396 KB Output is correct
8 Correct 2 ms 18396 KB Output is correct
9 Correct 3 ms 18396 KB Output is correct
10 Correct 3 ms 18396 KB Output is correct
11 Correct 2 ms 18396 KB Output is correct
12 Correct 1816 ms 20584 KB Output is correct
13 Correct 648 ms 20792 KB Output is correct
14 Correct 4327 ms 20792 KB Output is correct
15 Correct 4854 ms 20792 KB Output is correct
16 Correct 3317 ms 22972 KB Output is correct
17 Correct 4853 ms 27652 KB Output is correct
18 Correct 4530 ms 31880 KB Output is correct
19 Execution timed out 13040 ms 35512 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 35512 KB Output is correct
2 Correct 2 ms 35512 KB Output is correct
3 Correct 3 ms 35512 KB Output is correct
4 Correct 2 ms 35512 KB Output is correct
5 Correct 2 ms 35512 KB Output is correct
6 Correct 2 ms 35512 KB Output is correct
7 Correct 2 ms 35512 KB Output is correct
8 Correct 2 ms 35512 KB Output is correct
9 Correct 2 ms 35512 KB Output is correct
10 Correct 2 ms 35512 KB Output is correct
11 Correct 3 ms 35512 KB Output is correct
12 Correct 1746 ms 37676 KB Output is correct
13 Correct 621 ms 37960 KB Output is correct
14 Correct 4404 ms 37960 KB Output is correct
15 Correct 5137 ms 37960 KB Output is correct
16 Correct 3294 ms 40252 KB Output is correct
17 Correct 4715 ms 44856 KB Output is correct
18 Correct 4798 ms 49272 KB Output is correct
19 Execution timed out 13039 ms 52936 KB Time limit exceeded
20 Halted 0 ms 0 KB -