제출 #590245

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
590245		jeroenodb	게임 (IOI13_game)	C++17	0 / 100	1 ms	340 KiB

game

#include "game.h"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
int c;
ll ans=0;
struct node2 {
    int pos=-1,len;
    ll g=0,lazy=0;
    node2 *l=NULL, *r = NULL;
    node2(int n) : len(n) {}
    static ll total(node2* nd) {
        return nd?gcd(nd->g,nd->lazy):0LL;
    }
    void query(int a, int b) {
        if(b<0 or a>=len) return;
        if(a<=0 and b>=len-1) {
            ans = gcd(ans,g);
            ans = gcd(ans,lazy);
             return;
        }
        if(pos!=-1 and a<=pos and pos<=b) {
            ans = gcd(ans,lazy);
        }
        int mid = len/2;
        if(l) l->query(a,b);
        if(r) r->query(a-mid,b-mid);
    }
    void update(int y, ll v) {
        if(pos==-1) {
            pos=y;
            lazy=v;
            return;
        }
        if(y==pos) {
            lazy=v;
            return;
        }
        int mid = len/2;
        if(y<mid) {
            if(!l) l = new node2(mid);
            l->update(y,v);
        } else {
            if(!r) r = new node2(len-mid);
            r->update(y-mid,v);
        }
        g = gcd(total(l),total(r));
    }
};
struct node {
    node *l = NULL, *r = NULL;
    int len; // make it power of 2?
    node2 *sub = NULL;
    node(int n) : len(n) {}
    node() {}
    void query(int cc, int dd, int a,int b) {
        if(dd<0 or cc>=len) return;
        int mid = len/2;
        if(cc<=0 and dd>=len-1) {
            if(sub) sub->query(a,b);
            return;
        }
        if(l) l->query(cc,dd,a,b);
        if(r) r->query(cc-mid,dd-mid,a,b);
    }
    void update(int x, int y, ll v) {
        int mid = len/2;
        if(!sub) sub = new node2(c);
        sub->update(y,v);
        if(len==1) return;
        if(x<mid) {
            if(!l) l = new node(mid);
            l->update(x,y,v);
        } else {
            if(!r) r= new node(len-mid);
            r->update(x-mid,y,v);
        }
    }
} root;
 
void init(int R, int C) {
    c=C;
    root = node(R);
}
 
void update(int P, int Q, long long K) {
    /* ... */
    root.update(P,Q,K);
}
 
long long calculate(int P, int Q, int U, int V) {
    ans=0;
    root.query(P,U,Q,V);
    return ans;
}

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