| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 159574 |
2019-10-23T11:00:19 Z |
mhy908 |
Game (IOI13_game) |
C++14 |
|
3 ms |
504 KB |
#include "game.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define llinf 8987654321987654321
#define inf 1987654321
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
LL gcd(LL a, LL b){return b?gcd(b, a%b):a;}
struct SEGMENT_TREE
{
struct NODE{
NODE *l, *r;
LL p, lazy;
int st, fin, num;
NODE(int s, int e) : st(s), fin(e), l(NULL), r(NULL), num(0), p(0) {}
}*root;
SEGMENT_TREE(){root=new NODE(1, 1+1e9);}
void update(NODE* here, int num, LL in){
if(here->num==0||here->st==here->fin||here->num==num){
here->num=num;
here->lazy=in;
here->p=in;
return;
}
int mid=(here->st+here->fin)/2;
if(here->l==NULL)here->l=new NODE(here->st, mid);
if(here->r==NULL)here->r=new NODE(mid+1, here->fin);
if(num==here->num)here->lazy=in;
else if(mid>=num)update(here->l, num, in);
else update(here->r, num, in);
here->p=gcd(gcd(here->l->p, here->r->p), here->lazy);
}
LL query(NODE* here, int st, int fin){
if(here->p==0)return 0;
if(here->st>=st&&here->fin<=fin)return here->p;
if(here->st>fin||here->fin<st)return 0;
if(here->num>=st&&here->num<=fin)return gcd(gcd(query(here->l, st, fin), query(here->r, st, fin)), here->lazy);
else return gcd(query(here->l, st, fin), query(here->r, st, fin));
}
void update(int num, LL in){update(root, num, in);}
LL query(int st, int fin){return query(root, st, fin);}
};
struct TWOSEG
{
struct NODE{
NODE *l, *r;
SEGMENT_TREE seg;
int st, fin;
NODE(int s, int e) : st(s), fin(e), l(NULL), r(NULL){}
}*root;
TWOSEG(){root=new NODE(1, 1+1e9);}
void update(NODE* here, int numx, int numy, LL in){
here->seg.update(numy, in);
if(here->st==here->fin)return;
int mid=(here->st+here->fin)/2;
if(here->l==NULL)here->l=new NODE(here->st, mid);
if(here->r==NULL)here->r=new NODE(mid+1, here->fin);
if(mid>=numx)update(here->l, numx, numy, in);
else update(here->r, numx, numy, in);
}
LL query(NODE* here, int stx, int finx, int sty, int finy){
if(here==NULL)return 0;
if(here->st>=stx&&here->fin<=finx)return here->seg.query(sty, finy);
if(here->st>finx||here->fin<stx)return 0;
return gcd(query(here->l, stx, finx, sty, finy), query(here->r, stx, finx, sty, finy));
}
void update(int numx, int numy, LL in){update(root, numx, numy, in);}
LL query(int stx, int finx, int sty, int finy){return query(root, stx, finx, sty, finy);}
}tseg;
void init(int R, int C){}
void update(int p, int q, LL k){
tseg.update(p+1, q+1, k);
}
LL calculate(int p, int u, int q, int v){
return tseg.query(p+1, q+1, u+1, v+1);
}
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 constructor 'SEGMENT_TREE::NODE::NODE(int, int)':
game.cpp:18:17: warning: 'SEGMENT_TREE::NODE::fin' will be initialized after [-Wreorder]
int st, fin, num;
^~~
game.cpp:16:15: warning: 'SEGMENT_TREE::NODE* SEGMENT_TREE::NODE::l' [-Wreorder]
NODE *l, *r;
^
game.cpp:19:9: warning: when initialized here [-Wreorder]
NODE(int s, int e) : st(s), fin(e), l(NULL), r(NULL), num(0), p(0) {}
^~~~
game.cpp:18:22: warning: 'SEGMENT_TREE::NODE::num' will be initialized after [-Wreorder]
int st, fin, num;
^~~
game.cpp:17:12: warning: 'LL SEGMENT_TREE::NODE::p' [-Wreorder]
LL p, lazy;
^
game.cpp:19:9: warning: when initialized here [-Wreorder]
NODE(int s, int e) : st(s), fin(e), l(NULL), r(NULL), num(0), p(0) {}
^~~~
game.cpp: In constructor 'TWOSEG::NODE::NODE(int, int)':
game.cpp:52:17: warning: 'TWOSEG::NODE::fin' will be initialized after [-Wreorder]
int st, fin;
^~~
game.cpp:50:15: warning: 'TWOSEG::NODE* TWOSEG::NODE::l' [-Wreorder]
NODE *l, *r;
^
game.cpp:53:9: warning: when initialized here [-Wreorder]
NODE(int s, int e) : st(s), fin(e), l(NULL), r(NULL){}
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 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 |
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 |
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 |
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 |
3 ms |
484 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
