제출 #1136793

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1136793		t9unkubj	게임 (IOI13_game)	C++20	100 / 100	2317 ms	245448 KiB

game

#ifdef t9unkubj
#include"debug.cpp"
//#include"template_no_debug.h"
#else 
#include "game.h"
#define dbg(...) 199958
#endif

#undef _GLIBCXX_DEBUG
#pragma GCC optimize("O3")
using namespace std;
#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template<class T,class F>
bool chmin(T &x, F y){
    if(x>y){
        x=y;
        return true;
    }
    return false;
}
template<class T, class F>
bool chmax(T &x, F y){
    if(x<y){
        x=y;
        return true;
    }
    return false;
}
double pass_time=0;

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;
}
constexpr int M=1<<30;
struct segtree{
    struct Node{
        Node*l;
        Node*r;
        ll val;
        Node():l(nullptr),r(nullptr),val(0){}
    };
    static constexpr int cap=30;
    int used;
    vc<ll>val;
    vc<ll>pos;
    int mode;
    using np=Node*;
    np root;
    segtree()=default;
    void build(){
        mode=used=0;
        root=new Node();
    }
    inline void maker(np&x){
        if(x==nullptr)x=new Node();
    }
    ll access(np&r){
        if(r==nullptr)return 0;
        return r->val;
    }
    void internal_set(int l,int r,int i,ll x,np&now){
        if(l+1==r){
            now->val=x;
            return;
        }
        int mid=l+r>>1;
        
        
        if(l<=i&&i<mid){
            maker(now->l);
            internal_set(l,mid,i,x,now->l);
        }else{
            maker(now->r);
            internal_set(mid,r,i,x,now->r);
        }
        now->val=gcd2(access(now->l),access(now->r));
    }
    void set(int i,ll x){
        if(mode==0&&used<cap){
            rep(j,pos.size()){
                if(pos[j]==i){
                    val[j]=x;
                    return;
                }
            }
            val.push_back(x);
            pos.push_back(i);
            used++;
            return;
        }else{
            vc<pair<ll,ll>>ts;
            ts.reserve(val.size());
            mode=1;
            while(val.size()){
                auto v=val.back();
                auto p=pos.back();
                ts.push_back({v,p});
                val.pop_back();
                pos.pop_back();
            }
            for(auto&x:ts)set(x.second,x.first);
        }
        internal_set(0,M,i,x,root);
    }
    ll internal_prod(int nl,int nr,int l,int r,np&now){
        if(nr<=l||r<=nl){
            return 0;
        }
        if(l<=nl&&nr<=r){
            return now->val;
        }
        int mid=nl+nr>>1;
        return gcd2(can_can(nl,mid,l,r,now->l),
        can_can(mid,nr,l,r,now->r));
    }
    ll can_can(int nl,int nr,int l,int r,np&now){
        if(now==nullptr)return 0;
        return internal_prod(nl,nr,l,r,now);
    }
    ll prod(ll l,ll r){
        if(mode==0){
            ll res=0;
            rep(i,val.size()){
                if(l<=pos[i]&&pos[i]<r){
                    res=gcd2(res,val[i]);
                }
            }
            return res;
        }
        return internal_prod(0,M,l,r,root);
    }
};

struct Segtree{
    struct Node2{
        Node2*l;
        Node2*r;
        segtree* seg;
        Node2():l(nullptr),r(nullptr),seg(nullptr){}
    };
    using np2=Node2*;
    np2 root;
    Segtree()=default;
    void build(){
        root=new Node2();
        root->seg=new segtree();
        root->seg->build();
    }
    inline void maker(np2&x){
        if(x==nullptr)x=new Node2(),x->seg=new segtree(),x->seg->build();
    }
    ll PROD(ll l,ll r,np2&now){
        if(now==nullptr)return 0;
        return now->seg->prod(l,r);
    }
    void internal_set(int l,int r,int i,int j,ll x,np2&now){
        if(l+1==r){
            (now->seg)->set(j,x);
            return;
        }
        
        int mid=l+r>>1;
        
        if(l<=i&&i<mid){
            maker(now->l);
            internal_set(l,mid,i,j,x,now->l);
        }else{
            maker(now->r);     
            internal_set(mid,r,i,j,x,now->r);
        }

        now->seg->set(j,gcd2(PROD(j,j+1,now->l),PROD(j,j+1,now->r)));
    }
    void set(int i,int j,ll x){
        internal_set(0,M,i,j,x,root);
    }
    ll internal_prod(int nl,int nr,int l,int r,np2&now,ll L2,ll R2){
        if(nr<=l||r<=nl){
            return 0;
        }
        if(l<=nl&&nr<=r){
            return now->seg->prod(L2,R2);
        }
        int mid=nl+nr>>1;
        return gcd2(can_can(nl,mid,l,r,now->l,L2,R2),
        can_can(mid,nr,l,r,now->r,L2,R2));
    }
    ll can_can(int nl,int nr,int l,int r,np2&now,ll L2,ll R2){
        if(now==nullptr)return 0;
        return internal_prod(nl,nr,l,r,now,L2,R2);
    }
    ll prod(ll l,ll r,ll L2,ll R2){
        return internal_prod(0,M,l,r,root,L2,R2);
    }
};
Segtree seg;
void init(int R, int C) {
    seg.build();
}

void update(int P, int Q, long long K) {
    /* ... */
    seg.set(P,Q,K);
    dbg(seg.prod(P,P+1,Q,Q+1));
}

long long calculate(int P, int Q, int U, int V) {
    /* ... */
    return seg.prod(P,U+1,Q,V+1);
}
namespace judge{
    void run(){
        init(0,0);
        while(1){
            int t;
            cin>>t;
            if(t==1){
                int a,b,c;
                cin>>a>>b>>c;
                update(a,b,c);
            }else{
                int a,b,c,d;
                cin>>a>>b>>c>>d;
                dbg(calculate(a,b,c,d));
            }
        }
    }
};
//int main(){judge::run();}

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