oj.uz

Submission #159637

# Submission time Handle Problem Language Result Execution time Memory
159637 2019-10-23T16:17:45 Z mhy908 Game (IOI13_game) C++14
63 / 100
 4057 ms 256004 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->p=in;
            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);
    }
    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);
        if(here->st==here->fin){
            here->seg.update(numy, in);
            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 ll=here->l==NULL?0:here->l->seg.query(numy, numy);
        LL rr=here->r==NULL?0:here->r->seg.query(numy, numy);
        here->seg.update(numy, gcd(ll, rr));
    }
    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:88:17: warning: 'TWOSEG::NODE::fin' will be initialized after [-Wreorder]
         int st, fin;
                 ^~~
game.cpp:86:15: warning:   'TWOSEG::NODE* TWOSEG::NODE::l' [-Wreorder]
         NODE *l, *r;
               ^
game.cpp:89:9: warning:   when initialized here [-Wreorder]
         NODE(int s, int e) : st(s), fin(e), l(NULL), r(NULL), seg(){}
         ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 6 ms 1016 KB Output is correct
3 Correct 6 ms 1144 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 6 ms 1016 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 5 ms 1016 KB Output is correct
10 Correct 3 ms 760 KB Output is correct
11 Correct 3 ms 632 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 1666 ms 100592 KB Output is correct
5 Correct 1257 ms 100208 KB Output is correct
6 Correct 1729 ms 98428 KB Output is correct
7 Correct 1904 ms 98188 KB Output is correct
8 Correct 1179 ms 60280 KB Output is correct
9 Correct 1754 ms 98724 KB Output is correct
10 Correct 1668 ms 98084 KB Output is correct
11 Correct 2 ms 376 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 6 ms 988 KB Output is correct
3 Correct 7 ms 1140 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 6 ms 1020 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 5 ms 1016 KB Output is correct
10 Correct 3 ms 760 KB Output is correct
11 Correct 4 ms 632 KB Output is correct
12 Correct 2508 ms 37004 KB Output is correct
13 Correct 3431 ms 20860 KB Output is correct
14 Correct 872 ms 6264 KB Output is correct
15 Correct 3943 ms 30472 KB Output is correct
16 Correct 949 ms 50068 KB Output is correct
17 Correct 2731 ms 35628 KB Output is correct
18 Correct 4038 ms 51356 KB Output is correct
19 Correct 3495 ms 51360 KB Output is correct
20 Correct 3523 ms 50812 KB Output is correct
21 Correct 2 ms 376 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 6 ms 1016 KB Output is correct
3 Correct 6 ms 1144 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 6 ms 1016 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 6 ms 1036 KB Output is correct
10 Correct 4 ms 760 KB Output is correct
11 Correct 4 ms 532 KB Output is correct
12 Correct 1685 ms 100648 KB Output is correct
13 Correct 1231 ms 100148 KB Output is correct
14 Correct 1679 ms 98396 KB Output is correct
15 Correct 1720 ms 97956 KB Output is correct
16 Correct 1120 ms 60240 KB Output is correct
17 Correct 1760 ms 98752 KB Output is correct
18 Correct 1652 ms 98024 KB Output is correct
19 Correct 2533 ms 37168 KB Output is correct
20 Correct 3499 ms 20944 KB Output is correct
21 Correct 873 ms 6188 KB Output is correct
22 Correct 3952 ms 30620 KB Output is correct
23 Correct 1041 ms 49972 KB Output is correct
24 Correct 2482 ms 35756 KB Output is correct
25 Correct 4057 ms 51388 KB Output is correct
26 Correct 3602 ms 51592 KB Output is correct
27 Correct 3209 ms 50976 KB Output is correct
28 Runtime error 710 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 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 Correct 6 ms 1016 KB Output is correct
3 Correct 6 ms 1144 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 6 ms 1016 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 5 ms 1016 KB Output is correct
10 Correct 3 ms 760 KB Output is correct
11 Correct 3 ms 632 KB Output is correct
12 Correct 1665 ms 100888 KB Output is correct
13 Correct 1224 ms 100224 KB Output is correct
14 Correct 1666 ms 98348 KB Output is correct
15 Correct 1775 ms 98112 KB Output is correct
16 Correct 1061 ms 60136 KB Output is correct
17 Correct 1742 ms 98636 KB Output is correct
18 Correct 1671 ms 98104 KB Output is correct
19 Correct 2484 ms 37224 KB Output is correct
20 Correct 3474 ms 21112 KB Output is correct
21 Correct 874 ms 6320 KB Output is correct
22 Correct 4011 ms 30564 KB Output is correct
23 Correct 953 ms 50000 KB Output is correct
24 Correct 2451 ms 35736 KB Output is correct
25 Correct 3780 ms 51444 KB Output is correct
26 Correct 3721 ms 51580 KB Output is correct
27 Correct 3395 ms 51016 KB Output is correct
28 Runtime error 719 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -