oj.uz

Submission #159584

# Submission time Handle Problem Language Result Execution time Memory
159584 2019-10-23T11:42:29 Z mhy908 Game (IOI13_game) C++14
0 / 100
 5 ms 1016 KB 
#include "game.h"
#include <bits/stdc++.h>
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, 1+1e9);}
    void update(NODE* here, int num, LL in){
        if(here->st==here->fin){
            here->num=num;
            here->lazy=in;
            here->p=in;
            return;
        }
        int mid=(here->st+here->fin)/2;
        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);
    }
    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(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(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->l, 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);
}
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:11:17: warning: 'SEGMENT_TREE::NODE::fin' will be initialized after [-Wreorder]
         int st, fin, num;
                 ^~~
game.cpp:9:15: warning:   'SEGMENT_TREE::NODE* SEGMENT_TREE::NODE::l' [-Wreorder]
         NODE *l, *r;
               ^
game.cpp:12: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:11:22: warning: 'SEGMENT_TREE::NODE::num' will be initialized after [-Wreorder]
         int st, fin, num;
                      ^~~
game.cpp:10:12: warning:   'LL SEGMENT_TREE::NODE::p' [-Wreorder]
         LL p, lazy;
            ^
game.cpp:12: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:53:17: warning: 'TWOSEG::NODE::fin' will be initialized after [-Wreorder]
         int st, fin;
                 ^~~
game.cpp:51:15: warning:   'TWOSEG::NODE* TWOSEG::NODE::l' [-Wreorder]
         NODE *l, *r;
               ^
game.cpp:54:9: warning:   when initialized here [-Wreorder]
         NODE(int s, int e) : st(s), fin(e), l(NULL), r(NULL){}
         ^~~~

Subtask #1
0 / 10.0

# 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 -

Subtask #2
0 / 27.0

# 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 -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Incorrect 5 ms 1016 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Incorrect 5 ms 1016 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 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 -