oj.uz

Submission #411191

# Submission time Handle Problem Language Result Execution time Memory
411191 2021-05-24T14:52:46 Z faresbasbs Game (IOI13_game) C++14
63 / 100
 4339 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 ch2(node2* curr){
    if(curr->l == NULL){
        curr->l = new node2();
    }
    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 ;
    }
    ch2(curr);
    int mid = (l+r)/2;
    if(p <= mid){
        upd3(p,val,curr->l,l,mid);
    }else{
        upd3(p,val,curr->r,mid+1,r);
    }
    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 ;
    }
    ch2(curr),ch2(c2),ch2(c3);
    int mid = (l+r)/2;
    if(p <= mid){
        upd2(p,curr->l,c2->l,c3->l,l,mid);
    }else{
        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){
    // cout << p1 << " " << p2 << "  " << val << endl;
    if(l == r){
        upd3(p2,val,curr->segment,1,t);
        return ;
    }
    ch(curr);
    int mid = (l+r)/2;
    if(p1 <= mid){
        upd(p1,p2,val,curr->l,l,mid);
    }else{
        upd(p1,p2,val,curr->r,mid+1,r);
    }
    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;
    }
    ch2(curr);
    int mid = (l+r)/2;
    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);
    }
    ch(curr);
    int mid = (l+r)/2;
    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 4 ms 1228 KB Output is correct
3 Correct 4 ms 1228 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 4 ms 1100 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 552 KB Output is correct
9 Correct 3 ms 1188 KB Output is correct
10 Correct 2 ms 932 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 1 ms 332 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 460 KB Output is correct
4 Correct 1561 ms 152972 KB Output is correct
5 Correct 1167 ms 148068 KB Output is correct
6 Correct 1677 ms 195560 KB Output is correct
7 Correct 1629 ms 195256 KB Output is correct
8 Correct 1351 ms 147432 KB Output is correct
9 Correct 1657 ms 196868 KB Output is correct
10 Correct 1625 ms 195232 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 4 ms 1228 KB Output is correct
3 Correct 4 ms 1184 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 3 ms 1100 KB Output is correct
7 Correct 1 ms 428 KB Output is correct
8 Correct 1 ms 544 KB Output is correct
9 Correct 3 ms 1124 KB Output is correct
10 Correct 2 ms 972 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 2305 ms 41972 KB Output is correct
13 Correct 2699 ms 21008 KB Output is correct
14 Correct 1806 ms 7296 KB Output is correct
15 Correct 3101 ms 33092 KB Output is correct
16 Correct 1097 ms 60932 KB Output is correct
17 Correct 3801 ms 224748 KB Output is correct
18 Correct 4321 ms 234536 KB Output is correct
19 Correct 4140 ms 234552 KB Output is correct
20 Correct 4326 ms 233728 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 2 ms 332 KB Output is correct
2 Correct 4 ms 1228 KB Output is correct
3 Correct 4 ms 1316 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 5 ms 1100 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 4 ms 1196 KB Output is correct
10 Correct 2 ms 972 KB Output is correct
11 Correct 2 ms 544 KB Output is correct
12 Correct 1613 ms 153004 KB Output is correct
13 Correct 1183 ms 148024 KB Output is correct
14 Correct 1656 ms 195552 KB Output is correct
15 Correct 1600 ms 195176 KB Output is correct
16 Correct 1362 ms 147496 KB Output is correct
17 Correct 1703 ms 196784 KB Output is correct
18 Correct 1629 ms 195192 KB Output is correct
19 Correct 2299 ms 41940 KB Output is correct
20 Correct 2698 ms 21300 KB Output is correct
21 Correct 1815 ms 7292 KB Output is correct
22 Correct 3050 ms 33296 KB Output is correct
23 Correct 1068 ms 60924 KB Output is correct
24 Correct 3717 ms 224592 KB Output is correct
25 Correct 4339 ms 234724 KB Output is correct
26 Correct 4258 ms 234604 KB Output is correct
27 Correct 4226 ms 233928 KB Output is correct
28 Runtime error 421 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 5 ms 1228 KB Output is correct
3 Correct 4 ms 1228 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 3 ms 1100 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 548 KB Output is correct
9 Correct 4 ms 1100 KB Output is correct
10 Correct 2 ms 972 KB Output is correct
11 Correct 2 ms 544 KB Output is correct
12 Correct 1593 ms 152956 KB Output is correct
13 Correct 1171 ms 148096 KB Output is correct
14 Correct 1704 ms 195452 KB Output is correct
15 Correct 1629 ms 195296 KB Output is correct
16 Correct 1395 ms 147476 KB Output is correct
17 Correct 1671 ms 196804 KB Output is correct
18 Correct 1692 ms 195244 KB Output is correct
19 Correct 2318 ms 41972 KB Output is correct
20 Correct 2716 ms 21184 KB Output is correct
21 Correct 1821 ms 7360 KB Output is correct
22 Correct 3037 ms 33264 KB Output is correct
23 Correct 1057 ms 60940 KB Output is correct
24 Correct 3812 ms 224572 KB Output is correct
25 Correct 4319 ms 234492 KB Output is correct
26 Correct 4249 ms 234516 KB Output is correct
27 Correct 4205 ms 233724 KB Output is correct
28 Runtime error 404 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -