| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 20212 |
2016-04-11T07:28:01 Z |
murat |
Game (IOI13_game) |
C++ |
|
2 ms |
0 KB |
#include<bits/stdc++.h>
#include "game.h"
using namespace std;
const int inf = 1e9 + 5;
typedef long long ll;
const int N = 30000;
#define orta ((bas) + (son) >> 1)
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;
}
class node {
public:
node *l, *r;
int x, y, heap, size;
ll gcd, g;
node() {
l = r = NULL;
size = heap = x = y = gcd = g = 0;
}
};
typedef node* pnode;
pnode ST[N * 30], t1, t2, t3, t4;
int L[N * 30], R[N * 30], S = 1;
pnode make(int x, int y, ll g) {
pnode temp = new node;
temp->heap = rand() * rand();
temp->g = temp->gcd = g;
temp->l = temp->r = 0;
temp->size = 1;
temp->x = x;
temp->y = y;
return temp;
}
void relax(pnode &T) {
if(!T) return ;
T->size = 1;
T->gcd = T->g;
if(T->l) { T->size += T->l->size; T->gcd = gcd2(T->gcd, T->l->gcd); }
if(T->r) { T->size += T->r->size; T->gcd = gcd2(T->gcd, T->r->gcd); }
}
void merge(pnode &T, pnode l, pnode r) {
if(!l) { T = r; return ;}
if(!r) { T = l; return ;}
if(l->heap > r->heap) {
merge(l->r, l->r, r);
T = l;
}
else {
merge(r->l, l, r->l);
T = r;
}
relax(T);
}
void split(pnode T, pnode &l, pnode &r, int x) {
if(!T) { l = r = NULL; return ; }
int s = (T->l) ? T->l->size : 0;
if(s >= x) {
split(T->l, l, T->l, x);
r = T;
}
else {
split(T->r, T->r, r, x - s);
l = T;
}
relax(l); relax(r);
}
int lower_bound(pnode &T, int x, int y) {
if(!T) return 0;
if(make_pair(T->y, T->x) == make_pair(y, x)) return (T->l ? (T->l->size) : 0) + 1;
if(make_pair(T->y, T->x) < make_pair(y, x)) return lower_bound(T->r, x, y) + (T->l ? (T->l->size) : 0) + 1;
return lower_bound(T->l, x, y);
}
void change(pnode &T, int x, int y, ll g) {
if(!T) { T = make(x, y, g); return ;}
int tt = lower_bound(T, x, y);
split(T, t1, t2, tt);
split(t1, t3, t4, tt-1);
if(t4 && t4->x == x && t4->y == y) { t4->g = t4->gcd = g; merge(t1, t3, t4); }
else { merge(t1, t3, t4); merge(t1, t1, make(x, y, g)); }
merge(T, t1, t2);
}
void update(int k, int bas, int son, int x, int y, ll g) {
change(ST[k], x, y, g);
if(bas == son) return ;
if(x <= orta) {
if(!L[k]) { ST[S+1] = make(inf, inf, inf); L[k] = ++S; }
update(L[k], bas, orta, x, y, g);
}
else {
if(!R[k]) { R[k] = ++S; ST[S] = make(inf, inf, inf); }
update(R[k], orta + 1, son, x, y, g);
}
}
void print(pnode T) {
if(!T) return ;
print(T->l);
printf("-> %d %d %lld", T->x, T->y, T->g); cout << endl;
print(T->r);
}
ll query(int k, int bas, int son, int x, int y, int a, int b) {
if(!k || bas > y || son < x) return 0;
if(x <= bas && son <= y) {
int l = lower_bound(ST[k], 0, a);
int r = lower_bound(ST[k], 0, b+1) - 1;
split(ST[k], t1, t2, r);
split(t1, t3, t4, l-1);
ll cur = t4->gcd;
return cur;
}
return gcd2(query(L[k], bas, orta, x, y, a, b), query(R[k], orta + 1, son, x, y, a, b));
}
void init(int R, int C) {
srand(time(0));
ST[1] = make(inf, inf, inf);
}
void update(int P, int Q, long long K) {
update(1, 0, inf, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return query(1, 0, inf, P, U, Q, V);
}
Compilation message
/root/share/problems/files/104/grader.c: In function 'int main()':
/root/share/problems/files/104/grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
int res;
^
game.cpp: In function 'void update(int, int, int, int, int, ll)':
game.cpp:10:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
#define orta ((bas) + (son) >> 1)
^
game.cpp:106:13: note: in expansion of macro 'orta'
if(x <= orta) {
^
game.cpp:10:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
#define orta ((bas) + (son) >> 1)
^
game.cpp:108:27: note: in expansion of macro 'orta'
update(L[k], bas, orta, x, y, g);
^
game.cpp:10:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
#define orta ((bas) + (son) >> 1)
^
game.cpp:112:22: note: in expansion of macro 'orta'
update(R[k], orta + 1, son, x, y, g);
^
game.cpp: In function 'll query(int, int, int, int, int, int, int)':
game.cpp:10:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
#define orta ((bas) + (son) >> 1)
^
game.cpp:133:34: note: in expansion of macro 'orta'
return gcd2(query(L[k], bas, orta, x, y, a, b), query(R[k], orta + 1, son, x, y, a, b));
^
game.cpp:10:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
#define orta ((bas) + (son) >> 1)
^
game.cpp:133:65: note: in expansion of macro 'orta'
return gcd2(query(L[k], bas, orta, x, y, a, b), query(R[k], orta + 1, son, x, y, a, b));
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
0 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
0 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
0 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
0 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
0 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
