| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 171262 |
2019-12-28T06:21:19 Z |
dennisstar |
Game (IOI13_game) |
C++11 |
|
3 ms |
504 KB |
#include "game.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
#define all(V) ((V).begin()), ((V).end())
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;
typedef vector<ll> vlm;
int R, C;
struct dty {
dty *l, *r;
ll dt, L, R; int Key;
int md;
dty(int k) {Key=k; dt=0; l=r=NULL;}
inline void upd(int y, ll val, int ys, int ye) {
md=(ys+ye)/2;
if (Key) {
if (Key==y) {dt=val; return ;}
if (Key<=md) { l=new dty(Key); l->dt=dt; }
else { r=new dty(Key); r->dt=dt; }
Key=0;
}
if (y<=md) {
if (!l) l=new dty(y);
l->upd(y, val, ys, md);
}
else {
if (!r) r=new dty(y);
r->upd(y, val, md+1, ye);
}
L=(l?l->dt:0);
R=(r?r->dt:0);
dt=__gcd(L, R);
}
inline ll get(int y1, int y2, int ys, int ye) {
md=(ys+ye)/2;
if (Key) return (y1<=Key&&Key<=y2)?dt:0;
if (y1<=ys&&ye<=y2) return dt;
L=R=0;
if (!(md<y1)) L=(l?(l->get(y1, y2, ys, md)):0);
if (md+1<=y2&&md+1<=ye) R=(r?r->get(y1, y2, md+1, ye):0);
return __gcd(L, R);
}
inline ll get(int y, int ys, int ye) {
md=(ys+ye)/2;
if (Key) return (y==Key?dt:0);
if (y<=md) return l?l->get(y, ys, md):0;
else return r?r->get(y, md+1, ye):0;
}
};
struct dtx {
dty *seg;
dtx *l, *r;
int md;
ll L, R;
dtx() {l=r=NULL; seg=NULL;}
inline void upd(int x, int y, ll val, int xs, int xe) {
if (!seg) seg=new dty(y);
if (xs==xe) {seg->upd(y, val, 1, C); return ;}
md=(xs+xe)/2;
if (x<=md) {
if (!l) l=new dtx();
l->upd(x, y, val, xs, md);
}
else {
if (!r) r=new dtx();
r->upd(x, y, val, md+1, xe);
}
L=(l?(l->seg->get(y, 1, C)):0);
R=(r?(r->seg->get(y, 1, C)):0);
seg->upd(y, __gcd(L, R), 1, C);
}
inline ll get(int x1, int y1, int x2, int y2, int xs, int xe) {
if (x1<=xs&&xe<=x2) return seg->get(y1, y2, 1, C);
md=(xs+xe)/2;
L=R=0;
if (x1<=md) L=(l?(l->get(x1, y1, x2, y2, xs, md)):0);
if (md+1<=x2&&md+1<=xe) R=(r?(r->get(x1, y1, x2, y2, md+1, xe)):0);
return __gcd(L, R);
}
};
dtx *root;
void init(int r_, int c_) {
R=r_, C=c_;
root=new dtx();
}
void update(int P, int Q, ll K) {
root->upd(P+1, Q+1, K, 1, R);
}
ll calculate(int P, int Q, int U, int V) {
return root->get(P+1, Q+1, U+1, V+1, 1, R);
}
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;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
376 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 |
1 ms |
376 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 |
3 ms |
476 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 |
3 ms |
504 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 |
1 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
