oj.uz

Submission #97129

# Submission time Handle Problem Language Result Execution time Memory
97129 2019-02-14T03:30:35 Z E869120 Game (IOI13_game) C++14
0 / 100
 4 ms 384 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

int cnts = 0;

long long gcd2(long long X, long long Y) {
	if (Y == 0) return X;
	return gcd2(Y, X % Y);
}

struct Node {
	public:
	long long val; int l, m, r;
};

class MeleeSegmentTree {
	public:
	vector<Node> dat; int size_;
	
	void init(int I) {
		size_ = 1;
		while (size_ < I) size_ *= 3;
		dat.push_back(Node{0LL, -1, -1});
	}
	void update_(unsigned int p, long long x, unsigned int cl, unsigned int cr, int u) {
		if (cr - cl == 1) { dat[u].val = x; return; }
		if (p * 3 < (cl + cl + cr)) {
			if (dat[u].l == -1) { dat[u].l = dat.size(); dat.push_back(Node{0LL, -1, -1}); }
			update_(p, x, cl, (cl + cl + cr) / 3, dat[u].l);
		}
		else if (p * 3 < (cl + cr + cr)) {
			if (dat[u].m == -1) { dat[u].m = dat.size(); dat.push_back(Node{0LL, -1, -1}); }
			update_(p, x, (cl + cl + cr) / 3, (cl + cr + cr) / 3, dat[u].m);
		}
		else {
			if (dat[u].r == -1) { dat[u].r = dat.size(); dat.push_back(Node{0LL, -1, -1}); }
			update_(p, x, (cl + cr + cr) / 3, cr, dat[u].r);
		}
		long long e1 = 0; if (dat[u].l >= 0) e1 = dat[dat[u].l].val;
		long long e2 = 0; if (dat[u].m >= 0) e2 = dat[dat[u].m].val;
		long long e3 = 0; if (dat[u].r >= 0) e3 = dat[dat[u].r].val;
		dat[u].val = gcd2(e1, gcd2(e2, e3));
	}
	void update(int p, long long x) {
		return update_((unsigned int)(p), x, 0, size_, 0);
	}
	long long query_(unsigned int l, unsigned int r, unsigned int a, unsigned int b, int u) {
		if (u == -1) return 0;
		if (l <= a && b <= r) {
			return dat[u].val;
		}
		if (r <= a || b <= l) return 0;
		long long P1 = query_(l, r, a, (a + a + b) / 3, dat[u].l);
		long long P2 = query_(l, r, (a + a + b) / 3, (a + b + b) / 3, dat[u].m);
		long long P3 = query_(l, r, (a + b + b) / 3, b, dat[u].r);
		return gcd2(P1, gcd2(P2, P3));
	}
	long long query(long long l, long long r) {
		return query_(l, r, 0, size_, 0);
	}
};

long long H, W;

struct Node2 {
	MeleeSegmentTree val; int l, r;
};

class RangedSegmentTree {
	public:
	vector<Node2>dat; int size_, AX, AY, BX, BY; MeleeSegmentTree BASE;
	
	void init(int I) {
		BASE.init(W);
		size_ = 1;
		while (size_ < I) size_ *= 2;
		dat.push_back(Node2{BASE, -1, -1});
	}
	void update_(int p, int q, long long x, int cl, int cr, int u) {
		if (cr - cl == 1) {
			//cout << "update " << u << " " << q << " " << x << endl;
			dat[u].val.update(q, x); return;
		}
		
		if (p < ((cl + cr) >> 1)) {
			if (dat[u].l == -1) { dat[u].l = dat.size(); dat.push_back(Node2{BASE, -1, -1}); }
			update_(p, q, x, cl, (cl + cr) >> 1, dat[u].l);
		}
		else {
			if (dat[u].r == -1) { dat[u].r = dat.size(); dat.push_back(Node2{BASE, -1, -1}); }
			update_(p, q, x, (cl + cr) >> 1, cr, dat[u].r);
		}
		long long e1 = 0; if (dat[u].l >= 0) e1 = dat[dat[u].l].val.query(q, q+1);
		long long e2 = 0; if (dat[u].r >= 0) e2 = dat[dat[u].r].val.query(q, q+1);
		//cout << "update " << u << " " << q << " " << gcd2(e1, e2) << " " << e1 << " " << e2 << endl;
		dat[u].val.update(q, gcd2(e1, e2));
	}
	void update(int p, int q, long long x) {
		return update_(p, q, x, 0, size_, 0);
	}
	long long query_(int l, int r, int u) {
		if (u == -1) return 0;
		if (AX <= l && r <= BX) {
			long long x = dat[u].val.query(AY, BY);
			//cout << "query " << l << " " << r << " " << u << " " << x << endl;
			return x;
		}
		if (r <= AX || BX <= l) return 0;
		long long e1 = query_(l, (l + r) >> 1, dat[u].l);
		long long e2 = query_((l + r) >> 1, r, dat[u].r);
		return gcd2(e1, e2);
	}
	long long query(int ax, int ay, int bx, int by) {
		bx++; by++;
		AX = ax; AY = ay; BX = bx; BY = by;
		return query_(0, size_, 0);
	}
};

RangedSegmentTree X;

void init(int R, int C) {
	H = R; W = C;
	X.init(H);
}

void update(int P, int Q, long long K) {
    X.update(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
	return X.query(P, Q, U, V);
}

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 2 ms 256 KB Output is correct
2 Incorrect 4 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

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

Subtask #3
0 / 26.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 20.0

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