oj.uz

Submission #306979

# Submission time Handle Problem Language Result Execution time Memory
306979 2020-09-26T16:00:08 Z sofapuden Game (IOI13_game) C++14
37 / 100
 13000 ms 10640 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;
    }
    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+33,0,R+33);
}

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:18:23: warning: 'tree::br' will be initialized after [-Wreorder]
   18 |  tree *ul, *ur, *bl, *br;
      |                       ^~
game.cpp:17:21: warning:   'll tree::val' [-Wreorder]
   17 |  ll lb, rb, ub, db, val;
      |                     ^~~
game.cpp:20:2: warning:   when initialized here [-Wreorder]
   20 |  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 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 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 1 ms 384 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 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1227 ms 10396 KB Output is correct
5 Correct 888 ms 10616 KB Output is correct
6 Correct 868 ms 7544 KB Output is correct
7 Correct 1033 ms 7416 KB Output is correct
8 Correct 530 ms 5368 KB Output is correct
9 Correct 929 ms 7544 KB Output is correct
10 Correct 860 ms 7160 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 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 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 1 ms 384 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 5277 ms 7844 KB Output is correct
13 Execution timed out 13009 ms 2920 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 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 1 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 1188 ms 10360 KB Output is correct
13 Correct 924 ms 10632 KB Output is correct
14 Correct 805 ms 7544 KB Output is correct
15 Correct 963 ms 7412 KB Output is correct
16 Correct 506 ms 5368 KB Output is correct
17 Correct 873 ms 7544 KB Output is correct
18 Correct 828 ms 6904 KB Output is correct
19 Correct 5082 ms 7872 KB Output is correct
20 Execution timed out 13076 ms 2456 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 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 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1219 ms 10304 KB Output is correct
13 Correct 898 ms 10640 KB Output is correct
14 Correct 866 ms 7676 KB Output is correct
15 Correct 1031 ms 7544 KB Output is correct
16 Correct 558 ms 5496 KB Output is correct
17 Correct 939 ms 7544 KB Output is correct
18 Correct 872 ms 7032 KB Output is correct
19 Correct 5329 ms 7872 KB Output is correct
20 Execution timed out 13089 ms 2852 KB Time limit exceeded
21 Halted 0 ms 0 KB -