| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 159512 |
2019-10-23T01:13:45 Z |
gustjwkd1007 |
Game (IOI13_game) |
C++14 |
|
2 ms |
504 KB |
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int R, C;
LL gcd(LL a, LL b)
{
if (a > b)
return gcd(b, a);
if (a == 0)
return b;
return gcd(b%a, a);
}
struct node1D {
node1D *left=NULL, *right=NULL;
LL gap = 0;
void update1D(int a, int b,int chan,LL in)
{
// printf("//%d %d %d %lld//\n", a, b, chan, in);
if (a == b)
{
gap = in;
return;
}
int mid = (a + b) / 2;
if (chan <= mid)
{
if (left == NULL)
left = new node1D;
left->update1D(a, mid, chan, in);
}
else
{
if (right == NULL)
right = new node1D;
right->update1D(mid + 1, b, chan, in);
}
LL re = 0;
if (left != NULL)
re = gcd(re, left->gap);
if (right != NULL)
re = gcd(re, right->gap);
gap = re;
}
LL calculate1D(int a, int b, int x, int y)
{
// printf("//%d %d %d %d %lld//\n", a, b, x, y,gap);
if (x <= a && y >= b)
return gap;
if (x > b || y < a)
return 0;
LL re = 0;
int mid = (a + b) / 2;
if (left != NULL)
re = gcd(re, left->calculate1D(a, mid, x, y));
if (right != NULL)
re = gcd(re, right->calculate1D(mid + 1, b, x, y));
return re;
}
};
struct node2D {
node2D *left = NULL, *right = NULL;
node1D *myroot = new node1D;
void update2D(int a,int b, int chanR, int chanC, LL in)
{
// printf("t%d %d %d %d %lldt\n", a, b, chanR, chanC, in);
if (a == b)
{
myroot->update1D(1, C, chanC, in);
return;
}
int mid = (a + b) / 2;
LL re = 0;
if (chanR <= mid)
{
if (left == NULL)
left = new node2D;
left->update2D(a, mid, chanR, chanC, in);
}
else
{
if (right == NULL)
right = new node2D;
right->update2D(mid + 1, b, chanR, chanC, in);
}
myroot->update1D(1, C, chanC, calculate2D(1, R, chanR, chanR, chanC, chanC));
}
LL calculate2D(int a, int b, int Rx, int Ry,int Cx,int Cy)
{
// printf("t%d %d %d %d %d %dt\n", a, b, Rx, Ry, Cx, Cy);
if (Rx <= a && Ry >= b)
return myroot->calculate1D(1, C, Cx, Cy);
if (Rx > b || Ry < a)
return 0;
LL re = 0;
int mid = (a + b) / 2;
if (left != NULL)
re = gcd(re, left->calculate2D(a, mid, Rx, Ry, Cx, Cy));
if (right != NULL)
re = gcd(re, right->calculate2D(mid + 1, b, Rx, Ry, Cx, Cy));
return re;
}
};
node2D * root = new node2D;
void init(int r, int c)
{
R = r;
C = c;
}
void update(int P, int Q, LL k)
{
root->update2D(1, R, P, Q, k);
}
LL calculate(int P, int Q, int U, int V)
{
return root->calculate2D(1, R, P, U, Q, 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 member function 'void node2D::update2D(int, int, int, int, LL)':
game.cpp:73:6: warning: unused variable 're' [-Wunused-variable]
LL re = 0;
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
