| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 159621 |
2019-10-23T15:24:20 Z |
mhy908 |
Game (IOI13_game) |
C++14 |
|
5 ms |
1016 KB |
#include "game.h"
#include <bits/stdc++.h>
const int MAXR=10+1e9;
using namespace std;
typedef long long LL;
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), lazy(0) {}
}*root;
SEGMENT_TREE(){root=new NODE(1, MAXR);}
/*void update(NODE* here, int num, LL in){
printf("INY %d %d\n", here->st, here->fin);
if(here->st==here->fin){
here->num=num;
here->lazy=in;
here->p=in;
printf("INLAZY : %d %lld\n", here->num, here->lazy);
return;
}
int mid=(here->st+here->fin)/2;
if(here->num<=0){
here->num=num;
here->lazy=in;
//printf("INLAZY : %d %lld\n", here->num, here->lazy);
}
else if(num==here->num)here->lazy=in;
else if(mid>=num){
if(here->l==NULL)here->l=new NODE(here->st, mid);
update(here->l, num, in);
}
else{
if(here->r==NULL)here->r=new NODE(mid+1, here->fin);
update(here->r, num, in);
}
LL ll=here->l==nullptr?0:here->l->p;
LL rr=here->r==nullptr?0:here->r->p;
here->p=gcd(gcd(ll, rr), here->lazy);
//printf("Point : %d %d -> %lld\n", here->st, here->fin, here->p);
}
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;
LL ll=here->l==nullptr?0:query(here->l, st, fin);
LL rr=here->r==nullptr?0:query(here->r, st, fin);
if(here->num>=st&&here->num<=fin)return gcd(gcd(ll, rr), here->lazy);
else return gcd(ll, rr);
}*/
void update(NODE* here, int num, LL in){
//printf("INY %d %d\n", here->st, here->fin);
if(here->st==here->fin){
here->num=num;
//here->lazy=in;
here->p=in;
//printf("INLAZY : %d %lld\n", here->num, here->lazy);
return;
}
int mid=(here->st+here->fin)/2;
if(mid>=num){
if(here->l==NULL)here->l=new NODE(here->st, mid);
update(here->l, num, in);
}
else{
if(here->r==NULL)here->r=new NODE(mid+1, here->fin);
update(here->r, num, in);
}
LL ll=here->l==nullptr?0:here->l->p;
LL rr=here->r==nullptr?0:here->r->p;
here->p=gcd(ll, rr);
//printf("Point : %d %d -> %lld\n", here->st, here->fin, here->p);
}
LL query(NODE* here, int st, int fin){
if(here->st>=st&&here->fin<=fin)return here->p;
if(here->st>fin||here->fin<st)return 0;
LL ll=here->l==nullptr?0:query(here->l, st, fin);
LL rr=here->r==nullptr?0:query(here->r, st, fin);
return gcd(ll, rr);
}
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), seg(){}
}*root;
TWOSEG(){root=new NODE(1, MAXR);}
void update(NODE* here, int numx, int numy, LL in){
//printf("INX : %d %d : %d %lld\n", here->st, here->fin, numy, in);
here->seg.update(numy, in);
if(here->st==here->fin)return;
int mid=(here->st+here->fin)/2;
if(mid>=numx){
if(here->l==NULL)here->l=new NODE(here->st, mid);
update(here->l, numx, numy, in);
}
else{
if(here->r==NULL)here->r=new NODE(mid+1, here->fin);
update(here->r, numx, numy, in);
}
}
LL query(NODE* here, int stx, int finx, int sty, int finy){
if(here->st>=stx&&here->fin<=finx)return here->seg.query(sty, finy);
if(here->st>finx||here->fin<stx)return 0;
LL ll=(here->l==nullptr?0:query(here->l, stx, finx, sty, finy));
LL rr=(here->r==nullptr?0:query(here->r, stx, finx, sty, finy));
return gcd(ll, rr);
}
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);
//puts("=====");
}
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:12:17: warning: 'SEGMENT_TREE::NODE::fin' will be initialized after [-Wreorder]
int st, fin, num;
^~~
game.cpp:10:15: warning: 'SEGMENT_TREE::NODE* SEGMENT_TREE::NODE::l' [-Wreorder]
NODE *l, *r;
^
game.cpp:13:9: warning: when initialized here [-Wreorder]
NODE(int s, int e) : st(s), fin(e), l(NULL), r(NULL), num(0), p(0), lazy(0) {}
^~~~
game.cpp:12:22: warning: 'SEGMENT_TREE::NODE::num' will be initialized after [-Wreorder]
int st, fin, num;
^~~
game.cpp:11:12: warning: 'LL SEGMENT_TREE::NODE::p' [-Wreorder]
LL p, lazy;
^
game.cpp:13:9: warning: when initialized here [-Wreorder]
NODE(int s, int e) : st(s), fin(e), l(NULL), r(NULL), num(0), p(0), lazy(0) {}
^~~~
game.cpp: In constructor 'TWOSEG::NODE::NODE(int, int)':
game.cpp:92:17: warning: 'TWOSEG::NODE::fin' will be initialized after [-Wreorder]
int st, fin;
^~~
game.cpp:90:15: warning: 'TWOSEG::NODE* TWOSEG::NODE::l' [-Wreorder]
NODE *l, *r;
^
game.cpp:93:9: warning: when initialized here [-Wreorder]
NODE(int s, int e) : st(s), fin(e), l(NULL), r(NULL), seg(){}
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
1016 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
1016 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
1016 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
1016 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
