oj.uz

Submission #37980

# Submission time Handle Problem Language Result Execution time Memory
37980 2017-12-29T20:11:29 Z alenam0161 Game (IOI13_game) C++14
0 / 100
 26 ms 197332 KB 
#include "game.h"
#include <algorithm>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
const int N = ((int)1<<30)-1;
long long gcd2(long long X, long long Y) {
	long long tmp;
	while (X != Y && Y != 0) {
		tmp = X;
		X = Y;
		Y = tmp % Y;
	}
	return X;
}
struct node {
	long long val;
	node *lup, *ldown, *rup, *rdown;
	node(long long q = 0) {
		val = q;
		lup = ldown = rup= rdown=NULL;
	}
};
node *root;
node* get_node() {
	static node T[5000 * 1000];
	static int counter = 0;
	return &T[counter++];
}
inline long long get_(node *t) {
	return t ? t->val : 0ll;
}
inline bool in_(int llx, int lly, int rrx, int rry, int nx, int ny) {
	return  (llx <= nx&&lly <= ny&&rrx >= nx&&rry >= ny);
}
bool in_rect(int llx, int lly, int rrx, int rry, int nlx, int nly, int nrx, int nry) {
	return (nrx < llx || nry < lly || rrx < nlx || rry < nly)? 0:1;
}
void init(int R, int C) {
	/* ... */
}
void updatequard(int x, int y, long long val, node *&t, int nlx, int nly, int nrx, int nry) {
	if (!t)t = get_node();
//	cout << x << " " << y << endl;
//	cout << nlx << " " << nly << " " << nrx << " " << nry << endl;
//	cout << "level" << endl;
	if (nlx == nrx&&nry == nly) {
		t->val = val;
		return;
	}
	int mx = (nlx + nrx) / 2;
	int my = (nly + nry) / 2;
	// ldown
	if (in_(nlx, nly, mx, my, x, y))updatequard(x, y, val, t->ldown, nlx, nly, mx, my);
	// lup
	else if (in_(mx+1, nly, nrx, my, x, y))updatequard(x, y, val, t->lup, mx+1, nly, nrx, my);
	// rdown
	else if (in_(nlx, my+1, mx,nry, x, y))updatequard(x, y, val, t->rdown, nlx, my+1, mx, nry);
	//rup
	else updatequard(x, y, val, t->rup, mx+1, my+1, nrx, nry);
	t->val = gcd2(
		gcd2(get_(t->ldown), get_(t->lup)),
		gcd2(get_(t->rdown), get_(t->rup))
	);
}
void update(int P, int Q, long long K) {
	/* ... */
	updatequard(P, Q, K, root, 0, 0, N, N);
//	cout << "hi" << endl;
}
long long get(int llx, int lly, int rrx, int rry, node *t, int nlx, int nly, int nrx, int nry) {
	if (!t)return 0ll;
	if (in_(llx, lly, rrx, rry, nlx, nly) && in_(llx, lly, rrx, rry, nrx, nry))return t->val;
//	cout << llx << " " << lly << " " << rrx << " " << rry << " " << nlx << " " << nly << " " << nrx << " " << nry << endl;
	int mx = (nlx + nrx) / 2;
	int my = (nly + nry) / 2;
	long long cur = 0;
	// ldown
	if (in_rect(llx, lly, rrx, rry, nlx,nly,mx, my))cur = gcd2(cur, get(llx, lly, rrx, rry, t->ldown, nlx, nly, mx, my));
	// lup
	if (in_rect(llx, lly, rrx, rry,  mx + 1, nly, nrx, my))cur = gcd2(cur, get(llx, lly, rrx, rry, t->lup, mx+1, nly, nrx, my));
	// rdown
	if (in_rect(llx, lly, rrx, rry, nlx, my + 1, mx, nry))cur = gcd2(cur, get(llx, lly, rrx, rry, t->rdown, nlx, my+1, mx, nry));
	//rup
	if (in_rect(llx, lly, rrx, rry, mx + 1, my + 1, nrx, nry))cur = gcd2(cur, get(llx, lly, rrx, rry, t->ldown, mx+1,my+1, nrx,nry));
	return cur;
}

long long calculate(int P, int Q, int U, int V) {
	/* ... */
	return get(P,Q,U,V,root,0,0,N,N);
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 197332 KB Output is correct
2 Incorrect 26 ms 197332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 197332 KB Output is correct
2 Incorrect 23 ms 197332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 197332 KB Output is correct
2 Incorrect 26 ms 197332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 197332 KB Output is correct
2 Incorrect 23 ms 197332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 197332 KB Output is correct
2 Incorrect 23 ms 197332 KB Output isn't correct
3 Halted 0 ms 0 KB -