| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 224575 |
2020-04-18T12:45:06 Z |
T0p_ |
Game (IOI13_game) |
C++14 |
|
11 ms |
1024 KB |
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
int _R, _C;
struct node2
{
int l, r;
long long v;
node2 *L, *R;
node2(int a, int b)
{
l = a;
r = b;
v = 0;
L = R = NULL;
}
void extend()
{
if(!L && l != r)
{
int mid = (l+r)>>1;
L = new node2(l, mid);
R = new node2(mid+1, r);
}
}
};
struct node1
{
int l, r;
node2 *now;
node1 *L, *R;
node1(int a, int b, int c, int d)
{
l = a;
r = b;
now = new node2(c, d);
L = R = NULL;
}
void extend()
{
if(!L && l != r)
{
int mid = (l+r)>>1;
L = new node1(1, mid, 1, _C);
R = new node1(mid+1, r, 1, _C);
}
}
};
node1 *root;
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;
}
void init(int R, int C)
{
_R = R, _C = C;
root = new node1(1, R, 1, C);
}
void update2(node2 *seg, int q, long long k)
{
seg->extend();
if(!(seg->l <= q && q <= seg->r)) return void(cout << "OUT" << endl);
if(seg->l == seg->r)
{
seg->v = k;
return ;
}
int mid = (seg->l + seg->r)>>1;
update2(seg->L, q, k);
update2(seg->R, q, k);
seg->v = gcd2(seg->L->v, seg->R->v);
}
void update1(node1 *seg, int p, int q, long long k)
{
seg->extend();
if(!(seg->l <= p && p <= seg->r)) return void(cout << "OUT" << endl);
if(seg->l == seg->r)
{
update2(seg->now, q, k);
return ;
}
int mid = (seg->l + seg->r)>>1;
update1(seg->L, p, q, k);
update1(seg->R, p, q, k);
}
void update(int P, int Q, long long K) {
P++, Q++;
update1(root, P, Q, K);
}
long long query2(node2 *seg, int a, int b)
{
seg->extend();
if(seg->r < a || b < seg->l) return 0;
if(a <= seg->l && b <= seg->r) return seg->v;
return gcd2(query2(seg->L, a, b), query2(seg->R, a, b));
}
long long query1(node1 *seg, int a, int b, int c, int d)
{
seg->extend();
if(seg->r < a || b < seg->l) return 0;
if(a <= seg->l && seg->r <= b) return query2(seg->now, c, d);
return gcd2(query1(seg->L, a, b, c, d), query1(seg->R, a, b, c, d));
}
long long calculate(int P, int Q, int U, int V) {
P++, Q++, U++, V++;
return query1(root, 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;
^~~
game.cpp: In function 'void update2(node2*, int, long long int)':
game.cpp:81:9: warning: unused variable 'mid' [-Wunused-variable]
int mid = (seg->l + seg->r)>>1;
^~~
game.cpp: In function 'void update1(node1*, int, int, long long int)':
game.cpp:96:9: warning: unused variable 'mid' [-Wunused-variable]
int mid = (seg->l + seg->r)>>1;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Runtime error |
10 ms |
896 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Runtime error |
10 ms |
896 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Runtime error |
11 ms |
1024 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
256 KB |
Output is correct |
| 2 |
Runtime error |
9 ms |
896 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
