oj.uz

Submission #306982

# Submission time Handle Problem Language Result Execution time Memory
306982 2020-09-26T16:06:51 Z sofapuden Game (IOI13_game) C++14
37 / 100
 13000 ms 10872 KB 
#include "game.h"
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

ll gcd2(ll X, ll Y) {
    while (X != Y && Y != 0) {
        swap(X,Y);
        Y %= X;
    }
    if(X == 1)return -1;
    return X;
}

struct tree {
	ll lb, rb, ub, db, val;
	tree *ul, *ur, *bl, *br;
	
	tree () : ul(NULL), ur(NULL), bl(NULL), br(NULL), val(0) {}
	
	inline void initx(ll l, ll r, ll u, ll d){
		lb = l, rb = r, ub = u, db = d;
	}
	inline void extend(int num){
		ll mid1 = (lb+rb)>>1;
		ll mid2 = (ub+db)>>1;
		if(num == 0){
			if(!ul){
				ul = new tree;
				ul->initx(lb,mid1,ub,mid2);
			}
			return;
		}
		if(num == 1){
			if(!ur){
				ur = new tree;
				ur->initx(mid1+(lb == rb ? 0 : 1),rb,ub,mid2);
			}
			return;
		}
		if(num == 2){
			if(!bl){
				bl = new tree;
				bl->initx(lb,mid1,mid2+(ub == db ? 0 : 1),db);
			}
			return;
		}
		if(!br){
			br = new tree;
			br->initx(mid1+(lb == rb ? 0 : 1),rb,mid2+(ub == db ? 0 : 1),db);
		}
	}
	ll getGCD(ll l, ll r, ll u, ll d){
		if(r < lb || rb < l || d < ub || db < u){
			return 0;
		}
		if(l <= lb && rb <= r && u <= ub && db <= d){
			return val;
		}
		ll mid11 = (lb+rb)>>1, mid22 = (db+ub)>>1;
		ll ret = 0;
		if(l <= mid11 && u <= mid22){if(ul)ret = gcd2(ret,ul->getGCD(l,r,u,d));}
		if(ret == -1)return -1;
		if(mid11 < r && u <= mid22){if(ur)ret = gcd2(ret,ur->getGCD(l,r,u,d));}
		if(ret == -1)return -1;
		if(l <= mid11 && mid22 < d){if(bl)ret = gcd2(ret,bl->getGCD(l,r,u,d));}
		if(ret == -1)return -1;
		if(mid11 < r && mid22 < d){if(br)ret = gcd2(ret,br->getGCD(l,r,u,d));}		
		return ret;
	}
	void chan(ll p1, ll p2, ll ne){
		if(lb == rb && ub == db){
			val = ne;
			return;
		}
		ll ret = 0;
		ll mid11 = (lb+rb)>>1, mid22 = (db+ub)>>1;
		if(p1 <= mid11 && p2 <= mid22){extend(0);ul->chan(p1,p2,ne);}
		else if(p2 <= mid22){extend(1);ur->chan(p1,p2,ne);}
		else if(p1 <= mid11){extend(2);bl->chan(p1,p2,ne);}
		else {extend(3);br->chan(p1,p2,ne);}
		if(ul)ret = gcd2(ret,ul->val);
		if(ur)ret = gcd2(ret,ur->val);
		if(bl)ret = gcd2(ret,bl->val);
		if(br)ret = gcd2(ret,br->val);
		val = ret;
		return;
	}
};

tree *root = new tree();

void init(int R, int C) {
    root->initx(0,C+2,0,R+2);
}

void update(int P, int Q, long long K) {
    root->chan(Q,P,K);
}

long long calculate(int P, int Q, int U, int V) {
    return abs(root->getGCD(Q,V,P,U));
}

Compilation message

game.cpp: In constructor 'tree::tree()':
game.cpp:19:23: warning: 'tree::br' will be initialized after [-Wreorder]
   19 |  tree *ul, *ur, *bl, *br;
      |                       ^~
game.cpp:18:21: warning:   'll tree::val' [-Wreorder]
   18 |  ll lb, rb, ub, db, val;
      |                     ^~~
game.cpp:21:2: warning:   when initialized here [-Wreorder]
   21 |  tree () : ul(NULL), ur(NULL), bl(NULL), br(NULL), val(0) {}
      |  ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1000 ms 10360 KB Output is correct
5 Correct 683 ms 10744 KB Output is correct
6 Correct 770 ms 7676 KB Output is correct
7 Correct 899 ms 7416 KB Output is correct
8 Correct 529 ms 5240 KB Output is correct
9 Correct 772 ms 7416 KB Output is correct
10 Correct 304 ms 6904 KB Output is correct
11 Correct 1 ms 256 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 4951 ms 7928 KB Output is correct
13 Execution timed out 13100 ms 3188 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 987 ms 10464 KB Output is correct
13 Correct 685 ms 10872 KB Output is correct
14 Correct 757 ms 7544 KB Output is correct
15 Correct 906 ms 7416 KB Output is correct
16 Correct 543 ms 5368 KB Output is correct
17 Correct 743 ms 7416 KB Output is correct
18 Correct 301 ms 6904 KB Output is correct
19 Correct 4960 ms 8096 KB Output is correct
20 Execution timed out 13094 ms 3204 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 995 ms 10232 KB Output is correct
13 Correct 681 ms 10616 KB Output is correct
14 Correct 751 ms 7672 KB Output is correct
15 Correct 900 ms 7408 KB Output is correct
16 Correct 541 ms 5368 KB Output is correct
17 Correct 804 ms 7416 KB Output is correct
18 Correct 313 ms 7052 KB Output is correct
19 Correct 5026 ms 8004 KB Output is correct
20 Execution timed out 13096 ms 3320 KB Time limit exceeded
21 Halted 0 ms 0 KB -