oj.uz

Submission #306966

# Submission time Handle Problem Language Result Execution time Memory
306966 2020-09-26T15:26:22 Z Temmie Game (IOI13_game) C++17
0 / 100
 3 ms 1152 KB 
#include "game.h"
#include <bits/stdc++.h>

typedef long long ll;

const ll size = 1073741824;

// ew begin //
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;
}
// ew end //

struct Node {
	
	ll va, in;
	
	Node* ln, * rn;
	
	std::vector <std::pair <ll, ll>> was;
	
	Node(ll VAL = 0, ll IND = 0) : va(VAL), in(IND), ln(nullptr), rn(nullptr) { }
	
	~Node() {
		if (ln) delete(ln);
		if (rn) delete(rn);
	}
	
	void set(ll ind, ll val, ll l, ll r) {
		if (was.size()) {
			for (const auto& p : was) va = gcd2(va, p.first);
			if (!ln) ln = new Node(0, in * 2LL + 1LL);
			for (const auto& p : was)
				if (p.second < (l + r) >> 1LL) ln->was.push_back(p);
			if (!rn) rn = new Node(0, in * 2LL + 2LL);
			for (const auto& p : was)
				if (p.second >= (l + r) >> 1LL) rn->was.push_back(p);
			was.clear();
		}
		if (!(r - l - 1LL)) {
			va = val;
			return;
		}
		ll mid = (l + r) >> 1LL;
		if (ind < mid) {
			if (!ln) ln = new Node(0, in * 2LL + 1LL);
			ln->set(ind, val, l, mid);
		} else {
			if (!rn) rn = new Node(0, in * 2LL + 2LL);
			rn->set(ind, val, mid, r);
		}
		ll newv = 0;
		if (ln) newv = gcd2(newv, ln->va);
		if (rn) newv = gcd2(newv, rn->va);
		va = newv;
	}
	
	ll get(ll tl, ll tr, ll l, ll r) {
		if (was.size()) {
			for (const auto& p : was) va = gcd2(va, p.first);
			if (!ln) ln = new Node(0, in * 2LL + 1LL);
			for (const auto& p : was)
				if (p.second < (l + r) >> 1LL) ln->was.push_back(p);
			if (!rn) rn = new Node(0, in * 2LL + 2LL);
			for (const auto& p : was)
				if (p.second >= (l + r) >> 1LL) rn->was.push_back(p);
			was.clear();
		}
		if (l >= tr || r <= tl) return 0;
		if (l >= tl && r <= tr) return va;
		ll mid = (l + r) >> 1LL;
		ll re = 0;
		if (ln) re = gcd2(re, ln->get(tl, tr, l, mid));
		if (rn) re = gcd2(re, rn->get(tl, tr, mid, r));
		return re;
	}
	
};

struct SNode {
	
	ll in;
	
	Node* node;
	
	SNode* ln, * rn;
	
	SNode(ll IND = 0) : in(IND), node(new Node), ln(nullptr), rn(nullptr) { }
	
	~SNode() {
		if (node) delete(node);
		if (ln) delete(ln);
		if (rn) delete(rn);
	}
	
	void set(ll ind, ll nind, ll val, ll l, ll r) {
		if (!(r - l - 1LL)) {
			node->set(nind, val, 0, size);
			return;
		}
		ll mid = (l + r) >> 1LL;
		if(ind < mid) {
			if (!ln) ln = new SNode(in * 2LL + 1LL);
			ln->set(ind, nind, val, l, mid);
		} else {
			if (!rn) rn = new SNode(in * 2LL + 2LL);
			rn->set(ind, nind, val, mid, r);
		}
		node->was.push_back({ val, nind });
	}
	
	ll get(ll tl, ll tr, ll ntl, ll ntr, ll l, ll r) {
		if (l >= tr || r <= tl) return 0;
		if (l >= tl && r <= tr) return node->get(ntl, ntr, 0, size);
		ll mid = (l + r) >> 1LL;
		ll re = 0;
		if (ln) re = gcd2(re, ln->get(tl, tr, ntl, ntr, l, mid));
		if (rn) re = gcd2(re, rn->get(tl, tr, ntl, ntr, mid, r));
		return re;
	}
	
};

SNode* head = new SNode;

void init(int r, int c) { /* imagine needing it */ }

void update(int r, int c, ll val) { head->set(r, c, val, 0, size); }

ll calculate(int r1, int c1, int r2, int c2) { return head->get(r1, r2 + 1, c1, c2 + 1, 0, size); }

Subtask #1
0 / 10.0

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

Subtask #2
0 / 27.0

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

Subtask #3
0 / 26.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 20.0

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