답안 #306880

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
306880 2020-09-26T12:57:07 Z sofapuden 게임 (IOI13_game) C++14
10 / 100
13000 ms 256004 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){extend(0);ret = gcd2(ret,ul->getGCD(l,r,u,d));}
		if(mid11 < r && u <= mid22){extend(1);ret = gcd2(ret,ur->getGCD(l,r,u,d));}
		if(l <= mid11 && mid22 < d){extend(2);ret = gcd2(ret,bl->getGCD(l,r,u,d));}
		if(mid11 < r && mid22 < d){extend(3);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) {}
      |  ^~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 896 KB Output is correct
3 Correct 2 ms 896 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 896 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 256 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 Runtime error 257 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 896 KB Output is correct
3 Correct 2 ms 896 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 896 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Execution timed out 13048 ms 18080 KB Time limit exceeded
13 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 896 KB Output is correct
3 Correct 1 ms 896 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 896 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Runtime error 258 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 896 KB Output is correct
3 Correct 2 ms 928 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 2 ms 896 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Runtime error 260 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -