oj.uz

Submission #306869

# Submission time Handle Problem Language Result Execution time Memory
306869 2020-09-26T12:27:22 Z sofapuden Game (IOI13_game) C++14
0 / 100
 146 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;
tree *newTree();

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 = newTree();
			ur = newTree();
			bl = newTree();
			br = newTree();
			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 *newTree() {
    static int bufSize = 1e7;
    static tree buf[(int) 1e7];
    assert(bufSize);
    return &buf[--bufSize];
}

tree *root = newTree();

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:22:23: warning: 'tree::br' will be initialized after [-Wreorder]
   22 |  tree *ul, *ur, *bl, *br;
      |                       ^~
game.cpp:21:21: warning:   'll tree::val' [-Wreorder]
   21 |  ll lb, rb, ub, db, val;
      |                     ^~~
game.cpp:24:2: warning:   when initialized here [-Wreorder]
   24 |  tree () : ul(NULL), ur(NULL), bl(NULL), br(NULL), val(0) {}
      |  ^~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 146 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 143 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 140 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 140 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 144 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -