oj.uz

Submission #306868

# Submission time Handle Problem Language Result Execution time Memory
306868 2020-09-26T12:19:54 Z sofapuden Game (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(){
		if(!ul){
			ll mid1 = (lb+rb)>>1;
			ll mid2 = (ub+db)>>1;
			ul = new tree();
			ur = new tree();
			bl = new tree();
			br = new tree();
			ul->initx(lb,mid1,ub,mid2);
			ur->initx(mid1+(lb == rb ? 0 : 1),rb,ub,mid2);
			bl->initx(lb,mid1,mid2+(ub == db ? 0 : 1),db);
			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;
		}
		extend();
		return gcd2(gcd2(ul->getGCD(l,r,u,d),ur->getGCD(l,r,u,d)),gcd2(bl->getGCD(l,r,u,d),br->getGCD(l,r,u,d)));
	}
	void chan(ll p1, ll p2, ll ne){
		if(lb == rb && ub == db){
			val = ne;
			return;
		}
		extend();
		if(p1 <= ul->rb && p2 <= ul->db)ul->chan(p1,p2,ne);
		else if(p1 <= ul->rb)bl->chan(p1,p2,ne);
		else if(p2 <= ul->db)ur->chan(p1,p2,ne);
		else br->chan(p1,p2,ne);
		val = gcd2(gcd2(ul->val,ur->val),gcd2(bl->val,br->val));
		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 1 ms 256 KB Output is correct
2 Correct 2 ms 1152 KB Output is correct
3 Correct 2 ms 1152 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 2 ms 1152 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 1024 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 256 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Runtime error 247 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 1024 KB Output is correct
3 Correct 2 ms 1152 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 2 ms 1152 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 2 ms 1024 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Execution timed out 13085 ms 25440 KB Time limit exceeded
13 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 2 ms 1152 KB Output is correct
3 Correct 2 ms 1152 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 2 ms 1152 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 1152 KB Output is correct
11 Correct 1 ms 372 KB Output is correct
12 Runtime error 251 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 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 2 ms 1152 KB Output is correct
3 Correct 2 ms 1152 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 2 ms 1152 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 2 ms 1144 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Runtime error 246 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -