oj.uz

Submission #411194

# Submission time Handle Problem Language Result Execution time Memory
411194 2021-05-24T15:17:15 Z faresbasbs Game (IOI13_game) C++14
63 / 100
 3091 ms 256004 KB 
#include <bits/stdc++.h>
#include "game.h"
using namespace std;

struct node2{
    long long gc;
    node2 *l,*r;
    node2(){
        gc = 0;
        l = r = NULL;
    }
};

struct node1{
    node2 *segment;
    node1 *l,*r;
    node1(){
        segment = new node2();
        l = r = NULL;
    }
};

int t = pow(2,ceil(log2(1000000000)));
node1 *root = new node1();

void ch(node1* curr){
    if(curr->l == NULL){
        curr->l = new node1();
    }
    if(curr->r == NULL){
        curr->r = new node1();
    }
}

void chl(node1* curr){
    if(curr->l == NULL){
        curr->l = new node1();
    }
}

void chr(node1* curr){
    if(curr->r == NULL){
        curr->r = new node1();
    }
}

void ch2(node2* curr){
    if(curr->l == NULL){
        curr->l = new node2();
    }
    if(curr->r == NULL){
        curr->r = new node2();
    }
}

void ch2l(node2* curr){
    if(curr->l == NULL){
        curr->l = new node2();
    }
}

void ch2r(node2* curr){
    if(curr->r == NULL){
        curr->r = new node2();
    }
}

void upd3(int p , long long val , node2* curr , int l , int r){
    if(l == r){
        curr->gc = val;
        return ;
    }
    int mid = (l+r)/2;
    if(p <= mid){
        ch2l(curr),upd3(p,val,curr->l,l,mid);
    }else{
        ch2r(curr),upd3(p,val,curr->r,mid+1,r);
    }
    ch2(curr);
    curr->gc = __gcd(curr->l->gc,curr->r->gc);
}

void upd2(int p , node2* curr , node2* c2 , node2* c3 , int l , int r){
    curr->gc = __gcd(c2->gc,c3->gc);
    if(l == r){
        return ;
    }
    int mid = (l+r)/2;
    if(p <= mid){
        ch2l(curr),ch2l(c2),ch2l(c3),upd2(p,curr->l,c2->l,c3->l,l,mid);
    }else{
        ch2r(curr),ch2r(c2),ch2r(c3),upd2(p,curr->r,c2->r,c3->r,mid+1,r);
    }
}

void upd(int p1 , int p2 , long long val , node1 *curr , int l , int r){
    if(l == r){
        upd3(p2,val,curr->segment,1,t);
        return ;
    }
    int mid = (l+r)/2;
    if(p1 <= mid){
        chl(curr),upd(p1,p2,val,curr->l,l,mid);
    }else{
        chr(curr),upd(p1,p2,val,curr->r,mid+1,r);
    }
    ch(curr);
    upd2(p2,curr->segment,curr->l->segment,curr->r->segment,1,t);
}

void init(int R , int C){}

void update(int P , int Q , long long K){
    P++,Q++;
    upd(P,Q,K,root,1,t);
}

long long getgcd2(int a , int b , node2* curr , int l , int r){
    if(b < l || a > r){
        return 0;
    }
    if(a <= l && b >= r){
        return curr->gc;
    }
    int mid = (l+r)/2;
    if(b <= mid){
        ch2l(curr);
        return getgcd2(a,b,curr->l,l,mid);
    }else if(a > mid){
        ch2r(curr);
        return getgcd2(a,b,curr->r,mid+1,r);
    }
    ch2(curr);
    return __gcd(getgcd2(a,b,curr->l,l,mid),getgcd2(a,b,curr->r,mid+1,r));
}

long long getgcd(int a1 , int a2 , int b1 , int b2 , node1* curr , int l , int r){
    if(r < a1 || l > a2){
        return 0;
    }
    if(a1 <= l && a2 >= r){
        return getgcd2(b1,b2,curr->segment,1,t);
    }
    int mid = (l+r)/2;
    if(a2 <= mid){
        chl(curr);
        return getgcd(a1,a2,b1,b2,curr->l,l,mid);
    }else if(a1 > mid){
        chr(curr);
        return getgcd(a1,a2,b1,b2,curr->r,mid+1,r);
    }
    ch(curr);
    return __gcd(getgcd(a1,a2,b1,b2,curr->l,l,mid),getgcd(a1,a2,b1,b2,curr->r,mid+1,r));
}

long long calculate(int P, int Q, int U, int V){
    P++,Q++,U++,V++;
    return getgcd(P,U,Q,V,root,1,t);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 3 ms 972 KB Output is correct
3 Correct 3 ms 972 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 2 ms 844 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 420 KB Output is correct
9 Correct 2 ms 844 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 1 ms 344 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 920 ms 97796 KB Output is correct
5 Correct 685 ms 94144 KB Output is correct
6 Correct 1148 ms 132648 KB Output is correct
7 Correct 1121 ms 132404 KB Output is correct
8 Correct 920 ms 100420 KB Output is correct
9 Correct 1133 ms 133592 KB Output is correct
10 Correct 1038 ms 132252 KB Output is correct
11 Correct 1 ms 332 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 3 ms 972 KB Output is correct
3 Correct 3 ms 932 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 2 ms 844 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 2 ms 844 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 2 ms 484 KB Output is correct
12 Correct 1187 ms 29272 KB Output is correct
13 Correct 1594 ms 14116 KB Output is correct
14 Correct 857 ms 2528 KB Output is correct
15 Correct 1820 ms 22432 KB Output is correct
16 Correct 538 ms 40320 KB Output is correct
17 Correct 2580 ms 175164 KB Output is correct
18 Correct 2923 ms 183216 KB Output is correct
19 Correct 3091 ms 183252 KB Output is correct
20 Correct 2865 ms 182472 KB Output is correct
21 Correct 1 ms 332 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 268 KB Output is correct
2 Correct 3 ms 972 KB Output is correct
3 Correct 3 ms 972 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 420 KB Output is correct
6 Correct 3 ms 932 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 2 ms 844 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 940 ms 97888 KB Output is correct
13 Correct 716 ms 94148 KB Output is correct
14 Correct 1135 ms 132560 KB Output is correct
15 Correct 1117 ms 132292 KB Output is correct
16 Correct 893 ms 100404 KB Output is correct
17 Correct 1095 ms 133624 KB Output is correct
18 Correct 1047 ms 132180 KB Output is correct
19 Correct 1186 ms 29104 KB Output is correct
20 Correct 1586 ms 14116 KB Output is correct
21 Correct 838 ms 2536 KB Output is correct
22 Correct 1815 ms 22508 KB Output is correct
23 Correct 534 ms 40324 KB Output is correct
24 Correct 2568 ms 175048 KB Output is correct
25 Correct 2870 ms 183172 KB Output is correct
26 Correct 2898 ms 183168 KB Output is correct
27 Correct 2831 ms 182316 KB Output is correct
28 Runtime error 419 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 3 ms 972 KB Output is correct
3 Correct 3 ms 972 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 3 ms 844 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 2 ms 844 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 923 ms 97860 KB Output is correct
13 Correct 701 ms 94108 KB Output is correct
14 Correct 1134 ms 132448 KB Output is correct
15 Correct 1145 ms 132260 KB Output is correct
16 Correct 920 ms 100448 KB Output is correct
17 Correct 1198 ms 133564 KB Output is correct
18 Correct 1082 ms 132112 KB Output is correct
19 Correct 1198 ms 29028 KB Output is correct
20 Correct 1603 ms 14040 KB Output is correct
21 Correct 876 ms 2396 KB Output is correct
22 Correct 1821 ms 22428 KB Output is correct
23 Correct 558 ms 40132 KB Output is correct
24 Correct 2811 ms 175068 KB Output is correct
25 Correct 2988 ms 183116 KB Output is correct
26 Correct 2958 ms 183328 KB Output is correct
27 Correct 2867 ms 182248 KB Output is correct
28 Runtime error 405 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -