| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 12874 |
2015-01-15T19:59:44 Z |
ainta |
Game (IOI13_game) |
C++ |
|
0 ms |
1216 KB |
#include "game.h"
#include<stdio.h>
#include<algorithm>
using namespace std;
int MX, MY;
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 YSeg{
YSeg *c1, *c2;
int CK;
long long g;
YSeg(){ c1 = c2 = NULL; g = 0; }
void spread(int m){
if (!CK)return;
if (CK <= m)c1->CK = CK, c1->g = g;
else c2->CK = CK, c2->g = g;
CK = 0;
}
void Add(int b, int e, int y, long long t){
if (g == 0 || CK == y){
g = t;
CK = y;
return;
}
int m = (b + e) >> 1;
if (!c1)c1 = new YSeg(), c2 = new YSeg();
spread(m);
if (y <= m) c1->Add(b, m, y, t);
else c2->Add(m + 1, e, y, t);
g = gcd2(c1->g, c2->g);
}
void UDT(int b, int e, int y, YSeg *t1, YSeg *t2){
if (t1 && t1->CK && (t1->CK < b || t1->CK > e)) t1 = NULL;
if (t2 && t2->CK && (t2->CK < b || t2->CK > e)) t2 = NULL;
if (t1 == NULL && t2 == NULL){
g = 0;return;
}
int m = (b + e) >> 1;
YSeg *t3 = t1, *t4 = t2;
if (t1 == NULL){
g = t2->g;
if (t2->CK){ CK = t2->CK; return; }
}
if (t2 == NULL){
g = t1->g;
if (t1->CK){ CK = t1->CK; return; }
}
if (b == e){
if (t1 && t2)g = gcd2(t1->g, t2->g);
return;
}
if (!c1)c1 = new YSeg(), c2 = new YSeg();
spread(m);
if (t1 && t2)g = gcd2(t1->g, t2->g);
if (y <= m){
if (t1 && !t1->CK) t3 = t1->c1;
if (t2 && !t2->CK) t4 = t2->c1;
c1->UDT(b, m, y, t3, t4);
}
else{
if (t1 && !t1->CK) t3 = t1->c2;
if (t2 && !t2->CK) t4 = t2->c2;
c2->UDT(m + 1, e, y, t3, t4);
}
}
long long Calc(int b, int e, int by, int ey){
if (!g)return 0;
if (CK){
if (by <= CK && CK <= ey)return g;
return 0;
}
if (b == by && e == ey)return g;
int m = (b + e) >> 1;
long long r = 0;
if (by <= m) r = c1->Calc(b, m, by, min(ey, m));
if (ey > m)r = gcd2(c2->Calc(m + 1, e, max(by, m + 1), ey), r);
return r;
}
};
struct XSeg{
XSeg *c1, *c2;
YSeg *cy;
XSeg(){ c1 = c2 = NULL; cy = NULL;}
void Add(int b, int e, int x, int y, long long t){
if (!cy)cy = new YSeg();
if (b == e){
cy->Add(1, MY, y, t);
return;
}
int m = (b + e) >> 1;
if (!c1)c1 = new XSeg(), c2 = new XSeg();
if (x <= m) c1->Add(b, m, x, y, t);
else c2->Add(m + 1, e, x, y, t);
cy->UDT(1, MY, y, c1->cy, c2->cy);
}
long long Calc(int b, int e, int bx, int ex, int by, int ey){
if (b == bx && e == ex)return cy->Calc(1, MY, by, ey);
int m = (b + e) >> 1;
long long g = 0;
if (bx <= m && c1)g = c1->Calc(b, m, bx, min(m, ex), by, ey);
if (ex > m && c2)g = gcd2(g, c2->Calc(m + 1, e, max(bx, m + 1), ex, by, ey));
return g;
}
};
XSeg *root;
void init(int R, int C) {
MX = R, MY = C;
root = new XSeg();
}
void update(int P, int Q, long long K) {
root->Add(1, MX, P + 1, Q + 1, K);
}
long long calculate(int P, int Q, int U, int V) {
return root->Calc(1, MX, P + 1, U + 1, Q + 1, V + 1);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1216 KB |
SIGSEGV Segmentation fault |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1216 KB |
SIGSEGV Segmentation fault |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1216 KB |
SIGSEGV Segmentation fault |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1216 KB |
SIGSEGV Segmentation fault |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1216 KB |
SIGSEGV Segmentation fault |
| 2 |
Halted |
0 ms |
0 KB |
- |
