Submission #1165348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165348		ty_mxzhn	Game (IOI13_game)	C++20	100 / 100	2805 ms	44248 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;
}
struct SEGT{
    struct Node{
        int left , right;
        long long value;
        pair < int , long long > upd;
        Node():left(-1),right(-1),value(0),upd({-1,-1}){}
    };
    vector < Node > tree;
    SEGT(){
        tree.push_back(Node());
    }
    long long query(int ql , int qr , int ind=0 , int l=0 , int r=N){
        // cout << "query : " << l << " " << r << endl;
        if(l >= ql and r <= qr){
            if(ql <= tree[ind].upd.first and tree[ind].upd.first <= qr){
                // cout << "returning at with : " << tree[ind].value << " , " << tree[ind].upd.second << endl;
                return gcd2(tree[ind].value , tree[ind].upd.second);
            }
            else {
                // cout << "returning at with : " << tree[ind].value << endl;
                return tree[ind].value;
            }
        }
        else if(l > qr or r < ql)return 0;
        int mid = (l + r) / 2;   
        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);
        long long resme = ql <= tree[ind].upd.first and tree[ind].upd.first <= qr ? tree[ind].upd.second : 0;
        // cout << l << " " << r << " resme : " << resme << " , " << tree[ind].upd.first << " " << tree[ind].upd.second << endl;
        return gcd2(resme , gcd2(resleft , resright));
    }
    void update(int qp , long long qv , int ind=0 , int l=0 , int r=N){
        if(l == r){
            // cout << "set myself at : " << l << " " << r << " " << qv << endl;
            tree[ind].value = qv;
            return;
        }
        else if(tree[ind].upd.first == -1 or tree[ind].upd.first == qp){
            // cout << "added myself at : " << l << " " << r << " " << qp << " " << qv << endl;
            tree[ind].upd = {qp , qv};
            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;
            long long resme = tree[ind].upd.first == -1 ? 0 : tree[ind].upd.second;
            tree[ind].value = gcd2(resme , gcd2(resleft , resright));
            return;
        }
        int mid = (l + r) / 2;
        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;
        long long resme = tree[ind].upd.first == -1 ? 0 : tree[ind].upd.second;
        tree[ind].value = gcd2(resme , 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 = (l + r) / 2;
        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 = (l + r) / 2;
        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: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20