Submission #1165281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165281		ty_mxzhn	Game (IOI13_game)	C++20	0 / 100	201 ms	321536 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
const int N = 1e9 + 7;
long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
int get_midpoint(int l, int r) {//[l, r)
    int pow_2 = 1 << __lg(r-l);//bit_floor(unsigned(r-l));
    return min(l + pow_2, r - pow_2/2);
}
struct SEGT{
    struct Node{
        int left , right;
        long long value;
        Node():left(-1),right(-1),value(0){}
    };
    vector < Node > tree;
    SEGT(){
        tree.push_back(Node());
    }
    long long query(int ql , int qr , int ind=0 , int l=0 , int r=N){
        if(l >= ql and r <= qr)return tree[ind].value;
        else if(l > qr or r < ql)return 0;
        int mid = get_midpoint(l,r);
        long long resleft = tree[ind].left == -1 ? 0 : query(ql,qr,tree[ind].left,l,mid);
        long long resright = tree[ind].right == -1 ? 0 : query(ql,qr,tree[ind].right,mid+1,r);
        return gcd2(resleft , resright);
    }
    void update(int qp , long long qv , int ind=0 , int l=0 , int r=N){
        if(l == r){
            tree[ind].value = qv;
            return;
        }
        int mid = get_midpoint(l,r);
        if(qp <= mid){
            if(tree[ind].left == -1){
                tree[ind].left = sz(tree);
                tree.push_back(Node());
            }
            update(qp,qv,tree[ind].left,l,mid);
        }
        else{
            if(tree[ind].right == -1){
                tree[ind].right = sz(tree);
                tree.push_back(Node());
            }
            update(qp,qv,tree[ind].right,mid+1,r);
        }
        long long resleft = tree[ind].left == -1 ? 0 : tree[tree[ind].left].value;
        long long resright = tree[ind].right == -1 ? 0 : tree[tree[ind].right].value;
        tree[ind].value = gcd2(resleft , resright);
    }
};
struct SEGT2D{
    struct Node{
        int left , right;
        SEGT value;
        Node():left(-1),right(-1){}
    };
    vector < Node > tree;
    SEGT2D(){
        tree.push_back(Node());
    }
    long long query(int ql , int qr , int ql2 , int qr2 , int ind=0 , int l=0 , int r=N){
        if(l >= ql and r <= qr)return tree[ind].value.query(ql2,qr2);
        else if(l > qr or r < ql)return 0;
        int mid = get_midpoint(l,r);
        long long resleft = tree[ind].left == -1 ? 0 : query(ql,qr,ql2,qr2,tree[ind].left,l,mid);
        long long resright = tree[ind].right == -1 ? 0 : query(ql,qr,ql2,qr2,tree[ind].right,mid+1,r);
        return gcd2(resleft , resright);
    }
    void update(int qp , int qp2 , long long qv , int ind=0 , int l=0 , int r=N){
        if(l == r){
            tree[ind].value.update(qp2,qv);
            return;
        }
        int mid = get_midpoint(l,r);
        if(qp <= mid){
            if(tree[ind].left == -1){
                tree[ind].left = sz(tree);
                tree.push_back(Node());
            }
            update(qp,qp2,qv,tree[ind].left,l,mid);
        }
        else{
            if(tree[ind].right == -1){
                tree[ind].right = sz(tree);
                tree.push_back(Node());
            }
            update(qp,qp2,qv,tree[ind].right,mid+1,r);
        }
        long long resleft = tree[ind].left == -1 ? 0 : tree[tree[ind].left].value.query(qp2,qp2);
        long long resright = tree[ind].right == -1 ? 0 : tree[tree[ind].right].value.query(qp2,qp2);
        tree[ind].value.update(qp2 , gcd2(resleft , resright));
    }
} segt;
void init(int R, int C) {
    37;
}

void update(int P, int Q, long long K) {
    segt.update(P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
    return segt.query(min(P,U),max(P,U),min(Q,V),max(Q,V));
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20