oj.uz

Submission #306971

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

typedef long long ll;

using namespace std;

ll gcd2(ll X, ll Y) {
    ll tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    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(mid11 < r && u <= mid22){if(ur)ret = gcd2(ret,ur->getGCD(l,r,u,d));}
		if(l <= mid11 && mid22 < d){if(bl)ret = gcd2(ret,bl->getGCD(l,r,u,d));}
		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+4,0,R+4);
}

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 root->getGCD(Q,V,P,U);
}

Compilation message

game.cpp: In constructor 'tree::tree()':
game.cpp:20:23: warning: 'tree::br' will be initialized after [-Wreorder]
   20 |  tree *ul, *ur, *bl, *br;
      |                       ^~
game.cpp:19:21: warning:   'll tree::val' [-Wreorder]
   19 |  ll lb, rb, ub, db, val;
      |                     ^~~
game.cpp:22:2: warning:   when initialized here [-Wreorder]
   22 |  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 0 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 1 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 986 ms 14740 KB Output is correct
5 Correct 681 ms 14584 KB Output is correct
6 Correct 760 ms 12280 KB Output is correct
7 Correct 902 ms 11896 KB Output is correct
8 Correct 534 ms 9592 KB Output is correct
9 Correct 848 ms 12152 KB Output is correct
10 Correct 795 ms 11640 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 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 1 ms 256 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 5035 ms 7992 KB Output is correct
13 Execution timed out 13093 ms 3220 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 0 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 0 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 256 KB Output is correct
12 Correct 989 ms 13572 KB Output is correct
13 Correct 695 ms 14560 KB Output is correct
14 Correct 759 ms 12420 KB Output is correct
15 Correct 891 ms 12280 KB Output is correct
16 Correct 529 ms 9464 KB Output is correct
17 Correct 866 ms 12096 KB Output is correct
18 Correct 868 ms 11576 KB Output is correct
19 Correct 5160 ms 11748 KB Output is correct
20 Execution timed out 13078 ms 5676 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 288 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 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 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 993 ms 13808 KB Output is correct
13 Correct 690 ms 14460 KB Output is correct
14 Correct 751 ms 12280 KB Output is correct
15 Correct 905 ms 12024 KB Output is correct
16 Correct 525 ms 9720 KB Output is correct
17 Correct 832 ms 12152 KB Output is correct
18 Correct 806 ms 11768 KB Output is correct
19 Correct 4971 ms 11880 KB Output is correct
20 Execution timed out 13030 ms 5616 KB Time limit exceeded
21 Halted 0 ms 0 KB -