Submission #583568

#	Time	Username	Problem	Language	Result	Execution time	Memory
583568		thomas_li	Game (IOI13_game)	C++17	Compilation error	0 ms	0 KiB

game

#include <bits/stdc++.h>
using namespace std;
const int MM = 1e6;
mt19937 rng(42069);
struct INode{  // 28 bytes
    int c[2];  
    pair<int,int> pos; // y,x
    int64_t g,v; int pri;
    INode(int p, int q, int64_t k){
        pos = {q,p};
        g = v = k; 
        pri = rng();
        c[0] = c[1] = 0;
    }
    INode(){
        pos = {0,0};
        g = v = pri = 0; 
        c[0] = c[1] = 0;
    }
}ibuf[MM]; int ibuf_pos;
int64_t gcd(int64_t a, int64_t b) {
    if (!a || !b)
        return a | b;
    auto shift = __builtin_ctzll(a | b);
    a >>= __builtin_ctzll(a);
    do {
        b >>= __builtin_ctzll(b);
        if (a > b)
            swap(a, b);
        b -= a;
    } while (b);
    return a << shift;
}
void upd(int u){
    auto& cur = ibuf[u];
    cur.g = cur.v;
    if(cur.c[0]) cur.g = gcd(cur.g,ibuf[cur.c[0]].g);
    if(cur.c[1]) cur.g = gcd(cur.g,ibuf[cur.c[1]].g);
}
int alloc(int p, int q, int64_t k){
    auto& cur = ibuf[++ibuf_pos];  
    //cout << "creating new node: " << pos << " " << k << "\n";
    cur = INode(p,q,k);
    return ibuf_pos;
}
array<int,2> split(int u, pair<int,int> q){
    if(!u) return {0,0};   
    if(ibuf[u].pos >= q){
        auto p = split(ibuf[u].c[0],q); ibuf[u].c[0] = p[1];
        upd(u);
        return {p[0],u};
    } else{
        auto p = split(ibuf[u].c[1],q); ibuf[u].c[1] = p[0];
        upd(u);
        return {u,p[1]};
    }
}
int merge(int l, int r){
    if(!l) return r;
    if(!r) return l;
    int u;
    if(ibuf[l].pri > ibuf[r].pri) ibuf[l].c[1] = merge(ibuf[l].c[1],r),u = l;
    else ibuf[r].c[0] = merge(l,ibuf[r].c[0]), u = r;
    upd(u);
    return u;
}
int ins(int rt, int p, int q, int64_t k){
    auto[lft,tmp] = split(rt,{q,p});
    auto[same,rit] = split(tmp,{q,p+1});
    return merge(lft,merge(alloc(p,q,k),rit));
}
int64_t query_in(int& rt, int l, int r){
    auto[lft,tmp] = split(rt,{l,0}); 
    auto[in,rit] = split(tmp,{r+1,0});
    auto ans = ibuf[in].g; 
    rt = merge(lft,merge(in,rit));
    return ans;
}
struct Node{ // 16 bytes
    int l,r; // index in buffer
    int rt; // index in ibuf
}buf[MM*4];
int n,m,pos;
int alloc_out(){
    Node& rt = buf[++pos];
    rt.l = rt.r = 0; rt.rt = 0;
    return pos;
}


void print(int u){
    if(!u) return;
    print(ibuf[u].c[0]);
    cout << ibuf[u].v << " ";
    print(ibuf[u].c[1]);
}
// update all nodes that contain p in first layer
void upd(int u, int l, int r, int p, int q, int64_t k){
    //cout << "inserting to : " << l << " " << r << " " << p << " " << q << "\n";
    buf[u].rt = ins(buf[u].rt,p,q,k);
    //print(buf[u].rt); cout << "\n";
    if(l == r) return;
    int mid = (l+r)/2;
    if(p <= mid){
        if(!buf[u].l) buf[u].l = alloc_out();
        upd(buf[u].l,l,mid,p,q,k);
    } else{
        if(!buf[u].r) buf[u].r = alloc_out();
        upd(buf[u].r,mid+1,r,p,q,k);
    }
}

int64_t query(int u, int l, int r, int l_out, int r_out, int l_in, int r_in){
    if(l == l_out && r == r_out){
        return query_in(buf[u].rt,l_in,r_in);
    } 
    int mid = (l+r)/2;
    if(r_out <= mid){
        if(!buf[u].l) return 0;
        return query(buf[u].l,l,mid,l_out,r_out,l_in,r_in);
    } else if(l_out > mid){
        if(!buf[u].r) return 0;
        return query(buf[u].r,mid+1,r,l_out,r_out,l_in,r_in);
    } else{
        int64_t vl = buf[u].l == 0 ? 0 : query(buf[u].l,l,mid,l_out,mid,l_in,r_in); 
        int64_t vr = buf[u].r == 0 ? 0 : query(buf[u].r,mid+1,r,mid+1,r_out,l_in,r_in); 
        return gcd(vl,vr);
    }
}
void init(int R, int C){
    n = R, m = C; pos = ibuf_pos = 0;
    alloc_out(); // make root
}
void update(int P, int Q, long long K){
    upd(1,0,n-1,P,Q,K);          
}
long long calculate(int P, int Q, int U, int V){
    return query(1,0,n-1,P,U,Q,V);
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccs6Oz0G.o: in function `main':
grader.c:(.text.startup+0x6b): undefined reference to `init'
/usr/bin/ld: grader.c:(.text.startup+0xd0): undefined reference to `calculate'
/usr/bin/ld: grader.c:(.text.startup+0x13e): undefined reference to `update'
collect2: error: ld returned 1 exit status