Submission #411194

#	Time	Username	Problem	Language	Result	Execution time	Memory
411194		faresbasbs	Game (IOI13_game)	C++14	63 / 100	3091 ms	256004 KiB

game

#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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20