oj.uz

Submission #52192

# Submission time Handle Problem Language Result Execution time Memory
52192 2018-06-24T15:36:17 Z gnoor Game (IOI13_game) C++17
80 / 100
 13000 ms 387072 KB 
#include "game.h"

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

#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <queue>
//#include <iostream>

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;
}


struct node {
	pair<int,int> key;	//col,row
	int prior;
	long long val;
	long long gcd;
	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) {}

	~node() {
		if (l) delete l;
		if (r) delete r;
	}

	//static void print(node *x) {
		//if (!x) return;
		//print(x->l);
		////printf("%d,%lld ",x->key,x->val);
		//print(x->r);
	//}

	static void update(node *x) {
		if (!x) return;
		x->gcd=x->val;
		if (x->l) {
			x->gcd=gcd2(x->gcd,x->l->gcd);
		}
		if (x->r) {
			x->gcd=gcd2(x->gcd,x->r->gcd);
		}
	}	

	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) {
		//stepcnt++;
		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) {
		//stepcnt++;
		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 long long query(node* &x, int lo,int hi) {
		//printf("query %d %d\n",lo,hi);
		node *l,*m,*r;
		split(x,l,m,{lo,-1});
		split(m,m,r,{hi,1e9+7});
		//print(m);
		//printf("\n");
		long long ans=(m)?m->gcd:0;
		merge(m,m,r);
		merge(x,l,m);
		return ans;
	}
};

int maxR,maxC;
struct segnode {
	node *treap;										
	segnode *l,*r;

	segnode(): treap(0),l(0),r(0) {}

	static segnode* insert(segnode *x, int lo,int hi,int posR,int posC,long long val) {
		segnode *cur;
		if (x) cur=x;
		else cur=new segnode();
		bool res=node::change(cur->treap,{posC,posR},val);
		if (!res) node::insert(cur->treap,new node({posC,posR},val));	
		if (lo+1==hi) return cur;
		int m=(lo+hi)>>1;	
		if (posR<m) {
			cur->l=insert(cur->l,lo,m,posR,posC,val);
		} else {
			cur->r=insert(cur->r,m,hi,posR,posC,val);
		}
		return cur;			
	}	
	
	static long long query(segnode *x, int lo, int hi,int sR,int sC,int eR,int eC) {
		//printf("segquery %d %d\n",lo,hi);
		if (!x) return 0;
		if (sR>=hi||eR<lo) return 0;
		if (sR<=lo&&eR>=hi-1) return node::query(x->treap,sC,eC);
		int m=(lo+hi)>>1;
		return gcd2(query(x->l,lo,m,sR,sC,eR,eC),query(x->r,m,hi,sR,sC,eR,eC));
	}
};

segnode* root;

void init(int R, int C) {
	maxR=R;
	maxC=C;
}

void update(int P, int Q, long long K) {
	root=segnode::insert(root,0,maxR,P,Q,K);	
}


long long calculate(int P, int Q, int U, int V) {
	return segnode::query(root,0,maxR,P,Q,U,V);
}

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 252 KB Output is correct
2 Correct 5 ms 360 KB Output is correct
3 Correct 4 ms 440 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 2 ms 524 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 3 ms 652 KB Output is correct
10 Correct 4 ms 656 KB Output is correct
11 Correct 3 ms 676 KB Output is correct
12 Correct 2 ms 676 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 676 KB Output is correct
2 Correct 3 ms 676 KB Output is correct
3 Correct 2 ms 676 KB Output is correct
4 Correct 1316 ms 7408 KB Output is correct
5 Correct 621 ms 7820 KB Output is correct
6 Correct 2981 ms 7820 KB Output is correct
7 Correct 3408 ms 7820 KB Output is correct
8 Correct 2301 ms 7820 KB Output is correct
9 Correct 3462 ms 7820 KB Output is correct
10 Correct 3204 ms 7820 KB Output is correct
11 Correct 3 ms 7820 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7820 KB Output is correct
2 Correct 3 ms 7820 KB Output is correct
3 Correct 4 ms 7820 KB Output is correct
4 Correct 3 ms 7820 KB Output is correct
5 Correct 2 ms 7820 KB Output is correct
6 Correct 4 ms 7820 KB Output is correct
7 Correct 2 ms 7820 KB Output is correct
8 Correct 2 ms 7820 KB Output is correct
9 Correct 3 ms 7820 KB Output is correct
10 Correct 3 ms 7820 KB Output is correct
11 Correct 3 ms 7820 KB Output is correct
12 Correct 2037 ms 11932 KB Output is correct
13 Correct 9366 ms 11932 KB Output is correct
14 Correct 1462 ms 11932 KB Output is correct
15 Correct 10017 ms 20408 KB Output is correct
16 Correct 795 ms 26600 KB Output is correct
17 Correct 5445 ms 28232 KB Output is correct
18 Correct 10489 ms 37132 KB Output is correct
19 Correct 8404 ms 42576 KB Output is correct
20 Correct 9112 ms 47372 KB Output is correct
21 Correct 3 ms 47372 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 47372 KB Output is correct
2 Correct 5 ms 47372 KB Output is correct
3 Correct 3 ms 47372 KB Output is correct
4 Correct 3 ms 47372 KB Output is correct
5 Correct 3 ms 47372 KB Output is correct
6 Correct 3 ms 47372 KB Output is correct
7 Correct 2 ms 47372 KB Output is correct
8 Correct 3 ms 47372 KB Output is correct
9 Correct 3 ms 47372 KB Output is correct
10 Correct 4 ms 47372 KB Output is correct
11 Correct 3 ms 47372 KB Output is correct
12 Correct 1355 ms 47372 KB Output is correct
13 Correct 646 ms 47372 KB Output is correct
14 Correct 3119 ms 47372 KB Output is correct
15 Correct 3508 ms 47372 KB Output is correct
16 Correct 2241 ms 47372 KB Output is correct
17 Correct 3520 ms 47372 KB Output is correct
18 Correct 3199 ms 47372 KB Output is correct
19 Correct 2156 ms 50048 KB Output is correct
20 Correct 9806 ms 50048 KB Output is correct
21 Correct 1483 ms 50048 KB Output is correct
22 Correct 9580 ms 58696 KB Output is correct
23 Correct 742 ms 64864 KB Output is correct
24 Correct 5607 ms 66280 KB Output is correct
25 Correct 9994 ms 75476 KB Output is correct
26 Correct 8370 ms 80776 KB Output is correct
27 Correct 9259 ms 85576 KB Output is correct
28 Correct 2993 ms 113424 KB Output is correct
29 Correct 3614 ms 126396 KB Output is correct
30 Correct 11259 ms 128120 KB Output is correct
31 Correct 10202 ms 129468 KB Output is correct
32 Correct 1695 ms 129468 KB Output is correct
33 Correct 2995 ms 132396 KB Output is correct
34 Correct 1064 ms 162764 KB Output is correct
35 Correct 6064 ms 162764 KB Output is correct
36 Correct 11171 ms 183452 KB Output is correct
37 Correct 8805 ms 194328 KB Output is correct
38 Correct 10733 ms 204232 KB Output is correct
39 Correct 7533 ms 209192 KB Output is correct
40 Correct 3 ms 209192 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 209192 KB Output is correct
2 Correct 4 ms 209192 KB Output is correct
3 Correct 3 ms 209192 KB Output is correct
4 Correct 2 ms 209192 KB Output is correct
5 Correct 2 ms 209192 KB Output is correct
6 Correct 4 ms 209192 KB Output is correct
7 Correct 3 ms 209192 KB Output is correct
8 Correct 3 ms 209192 KB Output is correct
9 Correct 3 ms 209192 KB Output is correct
10 Correct 3 ms 209192 KB Output is correct
11 Correct 2 ms 209192 KB Output is correct
12 Correct 1323 ms 209192 KB Output is correct
13 Correct 607 ms 209192 KB Output is correct
14 Correct 3118 ms 209192 KB Output is correct
15 Correct 3421 ms 209192 KB Output is correct
16 Correct 2278 ms 209192 KB Output is correct
17 Correct 3244 ms 209192 KB Output is correct
18 Correct 3075 ms 209192 KB Output is correct
19 Correct 2150 ms 209192 KB Output is correct
20 Correct 9331 ms 209192 KB Output is correct
21 Correct 1304 ms 209192 KB Output is correct
22 Correct 9804 ms 209192 KB Output is correct
23 Correct 779 ms 214564 KB Output is correct
24 Correct 5436 ms 216148 KB Output is correct
25 Correct 9702 ms 225356 KB Output is correct
26 Correct 8566 ms 230604 KB Output is correct
27 Correct 8876 ms 235360 KB Output is correct
28 Correct 2595 ms 263080 KB Output is correct
29 Correct 3194 ms 276212 KB Output is correct
30 Correct 11352 ms 277904 KB Output is correct
31 Correct 11034 ms 279264 KB Output is correct
32 Correct 1858 ms 279264 KB Output is correct
33 Correct 3120 ms 282084 KB Output is correct
34 Correct 1031 ms 312564 KB Output is correct
35 Correct 6109 ms 312564 KB Output is correct
36 Correct 11080 ms 333248 KB Output is correct
37 Correct 9062 ms 343948 KB Output is correct
38 Correct 10660 ms 354064 KB Output is correct
39 Correct 3522 ms 387072 KB Output is correct
40 Correct 5428 ms 387072 KB Output is correct
41 Execution timed out 13019 ms 387072 KB Time limit exceeded
42 Halted 0 ms 0 KB -