# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
261013 |
2020-08-11T09:53:39 Z |
SamAnd |
게임 (IOI13_game) |
C++17 |
|
13000 ms |
47072 KB |
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const int T = 22003 * 30 * 30;
long long gcd(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
int R, C;
map<int, map<int, ll> > g;
void ubdy(int tlx, int trx, int tly, int try_, int x, int y, ll k, int posx, int posy)
{
if (tly == try_)
{
if (tlx == trx)
{
g[posx][posy] = k;
return;
}
g[posx][posy] = gcd(g[posx * 2][posy], g[posx * 2 + 1][posy]);
return;
}
int m = (tly + try_) / 2;
if (y <= m)
ubdy(tlx, trx, tly, m, x, y, k, posx, posy * 2);
else
ubdy(tlx, trx, m + 1, try_, x, y, k, posx, posy * 2 + 1);
g[posx][posy] = gcd(g[posx][posy * 2], g[posx][posy * 2 + 1]);
}
void ubdx(int tlx, int trx, int x, int y, ll k, int posx)
{
if (tlx == trx)
{
ubdy(tlx, trx, 0, C - 1, x, y, k, posx, 1);
return;
}
int m = (tlx + trx) / 2;
if (x <= m)
ubdx(tlx, m, x, y, k, posx * 2);
else
ubdx(m + 1, trx, x, y, k, posx * 2 + 1);
ubdy(tlx, trx, 0, C - 1, x, y, k, posx, 1);
}
ll qryy(int tly, int try_, int ly, int ry, int posx, int posy)
{
if (ly > ry)
return 0;
if (g.find(posx) == g.end())
return 0;
if (g[posx].find(posy) == g[posx].end())
return 0;
if (tly == ly && try_ == ry)
return g[posx][posy];
int m = (tly + try_) / 2;
return gcd(qryy(tly, m, ly, min(m, ry), posx, posy * 2),
qryy(m + 1, try_, max(m + 1, ly), ry, posx, posy * 2 + 1));
}
ll qryx(int tlx, int trx, int lx, int rx, int ly, int ry, int posx)
{
if (lx > rx)
return 0;
if (tlx == lx && trx == rx)
{
return qryy(0, C - 1, ly, ry, posx, 1);
}
int m = (tlx + trx) / 2;
return gcd(qryx(tlx, m, lx, min(m, rx), ly, ry, posx * 2),
qryx(m + 1, trx, max(m + 1, lx), rx, ly, ry, posx * 2 + 1));
}
void init(int R, int C)
{
::R = R;
::C = C;
}
void update(int P, int Q, long long K)
{
ubdx(0, R - 1, P, Q, K, 1);
}
long long calculate(int P, int Q, int U, int V)
{
return qryx(0, R - 1, P, U, Q, V, 1);
}
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;
^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
3 ms |
768 KB |
Output is correct |
3 |
Correct |
4 ms |
768 KB |
Output is correct |
4 |
Correct |
0 ms |
256 KB |
Output is correct |
5 |
Correct |
0 ms |
256 KB |
Output is correct |
6 |
Correct |
3 ms |
768 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
3 ms |
640 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
0 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
5769 ms |
38936 KB |
Output is correct |
5 |
Correct |
4166 ms |
38680 KB |
Output is correct |
6 |
Correct |
3840 ms |
36800 KB |
Output is correct |
7 |
Correct |
4081 ms |
36720 KB |
Output is correct |
8 |
Correct |
2371 ms |
23708 KB |
Output is correct |
9 |
Correct |
4493 ms |
36856 KB |
Output is correct |
10 |
Correct |
4468 ms |
36448 KB |
Output is correct |
11 |
Correct |
1 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
3 ms |
768 KB |
Output is correct |
3 |
Correct |
3 ms |
768 KB |
Output is correct |
4 |
Correct |
0 ms |
256 KB |
Output is correct |
5 |
Correct |
1 ms |
256 KB |
Output is correct |
6 |
Correct |
3 ms |
768 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
3 ms |
640 KB |
Output is correct |
10 |
Correct |
2 ms |
512 KB |
Output is correct |
11 |
Correct |
2 ms |
512 KB |
Output is correct |
12 |
Execution timed out |
13043 ms |
46872 KB |
Time limit exceeded |
13 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
4 ms |
768 KB |
Output is correct |
3 |
Correct |
4 ms |
768 KB |
Output is correct |
4 |
Correct |
0 ms |
256 KB |
Output is correct |
5 |
Correct |
1 ms |
256 KB |
Output is correct |
6 |
Correct |
4 ms |
768 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
3 ms |
640 KB |
Output is correct |
10 |
Correct |
2 ms |
512 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
5687 ms |
38756 KB |
Output is correct |
13 |
Correct |
4128 ms |
38880 KB |
Output is correct |
14 |
Correct |
3888 ms |
36948 KB |
Output is correct |
15 |
Correct |
4062 ms |
36616 KB |
Output is correct |
16 |
Correct |
2541 ms |
24004 KB |
Output is correct |
17 |
Correct |
4400 ms |
36892 KB |
Output is correct |
18 |
Correct |
4416 ms |
36216 KB |
Output is correct |
19 |
Execution timed out |
13045 ms |
46848 KB |
Time limit exceeded |
20 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
4 ms |
768 KB |
Output is correct |
3 |
Correct |
4 ms |
768 KB |
Output is correct |
4 |
Correct |
0 ms |
256 KB |
Output is correct |
5 |
Correct |
1 ms |
256 KB |
Output is correct |
6 |
Correct |
3 ms |
768 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
3 ms |
640 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
5732 ms |
38916 KB |
Output is correct |
13 |
Correct |
4157 ms |
38672 KB |
Output is correct |
14 |
Correct |
3818 ms |
37112 KB |
Output is correct |
15 |
Correct |
4094 ms |
36476 KB |
Output is correct |
16 |
Correct |
2569 ms |
23912 KB |
Output is correct |
17 |
Correct |
4382 ms |
36988 KB |
Output is correct |
18 |
Correct |
4556 ms |
36564 KB |
Output is correct |
19 |
Execution timed out |
13061 ms |
47072 KB |
Time limit exceeded |
20 |
Halted |
0 ms |
0 KB |
- |