# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
945751 |
2024-03-14T07:22:20 Z |
Der_Vlapos |
Game (IOI13_game) |
C++17 |
|
1875 ms |
256000 KB |
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define ll 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 tree
{
tree *l = NULL, *r = NULL;
int lv, rv;
ll res = 0;
tree(int lv, int rv) : lv(lv), rv(rv) {}
void enlarge()
{
int m = (lv + rv) >> 1;
if (l == NULL)
l = new tree(lv, m);
if (r == NULL)
r = new tree(m, rv);
}
ll get(int L, int R)
{
enlarge();
if (L <= lv and rv <= R)
{
return res;
}
if (rv <= L or R <= lv)
return 0;
assert(rv - lv > 0);
return gcd2(l->get(L, R), r->get(L, R));
}
void set(int pos, ll val)
{
enlarge();
if (rv - lv == 1)
{
res = val;
return;
}
assert(rv - lv > 0);
int m = (lv + rv) >> 1;
if (pos < m)
l->set(pos, val);
else
r->set(pos, val);
res = gcd2(l->res, r->res);
}
};
struct TREE
{
TREE *l = NULL, *r = NULL;
int lv, rv, maxY;
tree *res;
TREE(int lv, int rv, int maxY) : lv(lv), rv(rv), maxY(maxY) { res = new tree(0, maxY); }
void enlarge()
{
int m = (lv + rv) >> 1;
if (l == NULL)
l = new TREE(lv, m, maxY);
if (r == NULL)
r = new TREE(m, rv, maxY);
}
ll get(int L, int R, int lx, int ly)
{
enlarge();
if (L <= lv and rv <= R)
{
return res->get(lx, ly);
}
if (rv <= L or R <= lv)
return 0;
return gcd2(l->get(L, R, lx, ly), r->get(L, R, lx, ly));
}
void set(int x, int y, ll val)
{
enlarge();
if (rv - lv == 1)
{
res->set(y, val);
return;
}
int m = (lv + rv) >> 1;
if (x < m)
l->set(x, y, val);
else
r->set(x, y, val);
res->set(y, gcd2(l->res->get(y, y + 1), r->res->get(y, y + 1)));
}
};
TREE help(0, 1e9 + 10, 1e9 + 10);
void init(int R, int C)
{
/* ... */
}
void update(int P, int Q, long long K)
{
/* ... */
help.set(P, Q, K);
}
long long calculate(int P, int Q, int U, int V)
{
/* ... */
return help.get(min(P, U), max(P, U) + 1, min(Q, V), max(Q, V) + 1);
}
// /////////////////////
// #include <stdio.h>
// #include <stdlib.h>
// #include <assert.h>
// #include <vector>
// #include "game.h"
// #define MAX_SIZE 1000000000
// #define MAX_N 272000
// int main()
// {
// int R, C, N;
// int P, Q, U, V;
// long long K;
// int i, type;
// assert(scanf("%d", &R) == 1);
// assert(scanf("%d", &C) == 1);
// assert(scanf("%d", &N) == 1);
// init(R, C);
// std::vector<long long> answers;
// for (i = 0; i < N; i++)
// {
// assert(scanf("%d", &type) == 1);
// if (type == 1)
// {
// assert(scanf("%d%d%lld", &P, &Q, &K) == 3);
// update(P, Q, K);
// }
// else if (type == 2)
// {
// assert(scanf("%d%d%d%d", &P, &Q, &U, &V) == 4);
// answers.push_back(calculate(P, Q, U, V));
// }
// }
// for (auto answer : answers)
// {
// printf("%lld\n", answer);
// }
// return 0;
// }
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
600 KB |
Output is correct |
2 |
Correct |
5 ms |
3416 KB |
Output is correct |
3 |
Correct |
5 ms |
3420 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
1372 KB |
Output is correct |
6 |
Correct |
4 ms |
2908 KB |
Output is correct |
7 |
Correct |
1 ms |
856 KB |
Output is correct |
8 |
Correct |
1 ms |
1372 KB |
Output is correct |
9 |
Correct |
4 ms |
3164 KB |
Output is correct |
10 |
Correct |
3 ms |
2484 KB |
Output is correct |
11 |
Correct |
2 ms |
1368 KB |
Output is correct |
12 |
Correct |
1 ms |
688 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
604 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
860 KB |
Output is correct |
4 |
Runtime error |
891 ms |
256000 KB |
Execution killed with signal 9 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
600 KB |
Output is correct |
2 |
Correct |
5 ms |
3420 KB |
Output is correct |
3 |
Correct |
7 ms |
3420 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
2 ms |
1372 KB |
Output is correct |
6 |
Correct |
5 ms |
2908 KB |
Output is correct |
7 |
Correct |
1 ms |
860 KB |
Output is correct |
8 |
Correct |
1 ms |
1372 KB |
Output is correct |
9 |
Correct |
5 ms |
2996 KB |
Output is correct |
10 |
Correct |
3 ms |
2396 KB |
Output is correct |
11 |
Correct |
2 ms |
1372 KB |
Output is correct |
12 |
Correct |
1555 ms |
111888 KB |
Output is correct |
13 |
Correct |
1607 ms |
55016 KB |
Output is correct |
14 |
Correct |
1176 ms |
10728 KB |
Output is correct |
15 |
Correct |
1875 ms |
91500 KB |
Output is correct |
16 |
Correct |
924 ms |
176036 KB |
Output is correct |
17 |
Runtime error |
703 ms |
256000 KB |
Execution killed with signal 9 |
18 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
600 KB |
Output is correct |
2 |
Correct |
5 ms |
3420 KB |
Output is correct |
3 |
Correct |
5 ms |
3420 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
1372 KB |
Output is correct |
6 |
Correct |
5 ms |
2904 KB |
Output is correct |
7 |
Correct |
1 ms |
856 KB |
Output is correct |
8 |
Correct |
2 ms |
1372 KB |
Output is correct |
9 |
Correct |
5 ms |
3164 KB |
Output is correct |
10 |
Correct |
3 ms |
2392 KB |
Output is correct |
11 |
Correct |
2 ms |
1372 KB |
Output is correct |
12 |
Runtime error |
862 ms |
256000 KB |
Execution killed with signal 9 |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
600 KB |
Output is correct |
2 |
Correct |
5 ms |
3420 KB |
Output is correct |
3 |
Correct |
5 ms |
3252 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
1384 KB |
Output is correct |
6 |
Correct |
5 ms |
3060 KB |
Output is correct |
7 |
Correct |
1 ms |
864 KB |
Output is correct |
8 |
Correct |
1 ms |
1372 KB |
Output is correct |
9 |
Correct |
4 ms |
3168 KB |
Output is correct |
10 |
Correct |
3 ms |
2404 KB |
Output is correct |
11 |
Correct |
3 ms |
1780 KB |
Output is correct |
12 |
Runtime error |
818 ms |
256000 KB |
Execution killed with signal 9 |
13 |
Halted |
0 ms |
0 KB |
- |