oj.uz

Submission #788826

# Submission time Handle Problem Language Result Execution time Memory
788826 2023-07-20T16:26:49 Z Ludissey Game (IOI13_game) C++14
37 / 100
 13000 ms 71320 KB 
#include "game.h"
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <cstring>
#include <unordered_map>
#include <vector>
#include <fstream>
#include <bitset>
#include <tuple>
#include <cmath>
#include <cstdint>
#include <stack>
#include <cassert>
#include <cstdio>
#include <queue>
#include <iterator>
#include <iomanip>
#include <algorithm>
#include <sstream>

const int MAX_C = 100000;
const int MAX_R = 100;

int r, c;

using namespace std;
#define int long long

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 {
	node* left, * right;
	int gcd;

	void updates() {
		gcd = gcd2(left->gcd, right->gcd);
	}
};
vector<node*> roots;

int query(node* root, int left, int right, int qLeft, int qRight) {
	if (left > qRight || right < qLeft) return 0;
	if (left >= qLeft && right <= qRight) return root->gcd;

	int mid = (left + right) / 2;
	return gcd2(query(root->left, left, mid, qLeft, qRight), query(root->right, mid + 1, right, qLeft, qRight));
}

void update_(node* root, int left, int right, int point, int nValue) {
	int qLeft, qRight;
	qLeft = qRight = point;
	if (left > qRight || right < qLeft) return;

	if (left >= qLeft && right <= qRight) {
		root->gcd = nValue;
		return;
	}

	int mid = (left + right) / 2;
	update_(root->left, left, mid, point, nValue);

	update_(root->right, mid + 1, right, point, nValue);

	root->updates();
}

void build(node* root, int left, int right) {
	if (left == right) {
		root->gcd = 0;
		return;
	}
	int mid = (left + right) / 2;

	root->left = new node{ NULL, NULL, 0 };
	root->right = new node{ NULL, NULL, 0 };

	build(root->left, left, mid);
	build(root->right, mid + 1, right);

	root->updates();
}

void destroy(node* root) {
	if (root->left) destroy(root->left);
	if (root->right) destroy(root->right);
	delete root;
}

void init(signed R, signed C) {
	r = R;
	c = C;
	roots.resize(r);
	for (int i = 0; i < r; i++)
	{
		roots[i] = new node{ NULL, NULL, 0 };
		build(roots[i], 0, c - 1);
	}
	vector<node*> rootasd=roots;
	return;
}

void update(signed P, signed Q, long long K) {
	update_(roots[P], 0, c - 1, Q, K);
}


long long calculate(signed P, signed Q, signed U, signed V) {
	int gcd = 0;
	for (int i = P; i <= U; i++)
	{
		gcd = gcd2(query(roots[i], 0, c - 1, Q, V), gcd);
	}
	return gcd;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 816 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 1 ms 300 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 830 ms 71312 KB Output is correct
5 Correct 551 ms 71132 KB Output is correct
6 Correct 1012 ms 68584 KB Output is correct
7 Correct 995 ms 68276 KB Output is correct
8 Correct 943 ms 68752 KB Output is correct
9 Correct 1157 ms 68336 KB Output is correct
10 Correct 1124 ms 68044 KB Output is correct
11 Correct 1 ms 308 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 1 ms 812 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 852 KB Output is correct
10 Correct 1 ms 812 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Execution timed out 13109 ms 64500 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 212 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 808 KB Output is correct
6 Correct 1 ms 812 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 932 KB Output is correct
11 Correct 1 ms 908 KB Output is correct
12 Correct 1047 ms 71320 KB Output is correct
13 Correct 516 ms 71112 KB Output is correct
14 Correct 1058 ms 68596 KB Output is correct
15 Correct 1033 ms 68400 KB Output is correct
16 Correct 919 ms 68676 KB Output is correct
17 Correct 1124 ms 68456 KB Output is correct
18 Correct 980 ms 67964 KB Output is correct
19 Execution timed out 13063 ms 64492 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 808 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 911 ms 71284 KB Output is correct
13 Correct 512 ms 71196 KB Output is correct
14 Correct 1043 ms 68604 KB Output is correct
15 Correct 1051 ms 68272 KB Output is correct
16 Correct 999 ms 68752 KB Output is correct
17 Correct 1065 ms 68532 KB Output is correct
18 Correct 1004 ms 68044 KB Output is correct
19 Execution timed out 13086 ms 64424 KB Time limit exceeded
20 Halted 0 ms 0 KB -