oj.uz

Submission #411190

# Submission time Handle Problem Language Result Execution time Memory
411190 2021-05-24T14:51:30 Z faresbasbs Game (IOI13_game) C++14
0 / 100
 4 ms 1176 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 < a2 || l > a1){
        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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 4 ms 1100 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
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 Incorrect 1 ms 460 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 3 ms 1176 KB Output isn't correct
3 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 Incorrect 3 ms 1100 KB Output isn't correct
3 Halted 0 ms 0 KB -