Submission #1090773

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1090773	2024-09-18T18:01:04 Z	vjudge1	Game (IOI13_game)	C++17	Compilation error	0 ms	0 KB

game

#include <bits/stdc++.h>
//#include "game.h"
using namespace std;



#define int long long
#define ar array

const int INF = 1e18;

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 Teapy{
    struct Node{
        int h;
        ar<int, 2> b;
        Node *l, *r;
        int val;
        int g;
    
        Node(ar<int, 2> ind, int v){
            val = v;
            g = v;
            b = ind;
            h = rand();
            l = r = nullptr;
        };
    
        void merge(){
            g = val;
            if (l) g = gcd2(g, l->g);
            if (r) g = gcd2(g, r->g);
        }
    };
    Node* root;
    
    Teapy(){
        root = nullptr;
    }
    
    void split(Node* k, Node* &l, Node* &r, ar<int, 2> val){
        if (!k) return;
        if (k->b <= val){
            l = k;
            Node* tmp = nullptr;
            split(k->r, tmp, r, val);
            l->r = tmp;
        }
        else{
            r = k;
            Node* tmp = nullptr;
            split(k->l, l, tmp, val);
            r->l = tmp;
        }
        if (l) l->merge();
        if (r) r->merge();
    }
    
    void merge(Node* L, Node* R, Node* &res){
        if (!L){
            res = R;
            return;
        }
        if (!R){
            res = L;
            return;
        }
        if (L->h > R->h){
            Node* tmp = nullptr;;
            merge(L->r, R, tmp);
            L->r = tmp;
            res = L;
        }
        else{
            Node* tmp = nullptr;
            merge(L, R->l, tmp);
            R->l = tmp;
            res = R;
        }
        if (res) res->merge();
    }
    
    int qry(int l, int r){
        Node* a = nullptr;
        Node* b = nullptr;
        Node* c = nullptr;
        Node* d = nullptr;
        split(root, a, b, {l - 1, INF});
        split(b, c, d, {r, INF});
        int ans = 0;
        if (c) ans = c->g;
        Node* tmp;
        merge(a, c, tmp);
        Node* tmp2;
        merge(tmp, d, root);
        return ans;
    }
    
    void upd(ar<int, 2> ind, int val){
        Node* a = nullptr;
        Node* b = nullptr;
        Node* c = nullptr;
        Node* d = nullptr;
        split(root, a, b, {ind[0], ind[1] - 1});
        split(b, c, d, ind);
        if (!c) c = new Node(ind, val);
        c->val = val;
        c->g = val;
        Node* tmp = nullptr;
        merge(a, c, tmp);
        merge(tmp, d, root);
    }
};
    
    
struct Seggy{
    struct Node{
        Node *l, *r;
        Teapy *t;
        Node(){
            t = new Teapy();
            l = r = nullptr;
        }
    };
    
    int n;
    
    Node* root;
    Seggy(){
        root = new Node();
    }
    
    Seggy(int _n){
        root = new Node();
        n = _n;
        srand(time(nullptr));
    }
    
    void upd(Node* k, int tl, int tr, int x, int y, int v){
        k->t->upd({y, x}, v);
        if (tl == tr) return;
        int tm = (tl + tr) / 2;
        if (x <= tm){
            if (!k->l) k->l = new Node();
            upd(k->l, tl, tm, x, y, v);
        }
        else{
            if (!k->r) k ->r = new Node();
            upd(k->r, tm + 1, tr, x, y, v);
        }
    }
    
    int qry(Node* k, int tl, int tr, int l, int r, ar<int, 2> v){
        if (l > tr || tl > r) return 0;
        if (l <= tl && tr <= r) return k->t->qry(v[0], v[1]);
        int mid = (tl + tr) / 2;
        int ans = 0;
        if (l <= mid && k->l)ans = gcd2(ans, qry(k->l, tl, mid, l, r, v));
        if (r > mid && k->r)ans = gcd2(ans, qry(k->r, mid + 1, tr, l, r, v));
        
        return ans;
    }
    
    void upd(int sx, int sy, int val){
        upd(root, 0, n - 1, sx, sy, val);
    }
    
    int qry(int a, int b, int c, int d){
        return qry(root, 0, n - 1, a, b, {c, d});
    }
};
    
Seggy s;
    
void init(signed R, signed C) {
    s = Seggy(R);
}
    
void upd(signed P, signed Q, long long K) {
    s.upd(P, Q , K);
}
    
long long calculate(signed P, signed Q, signed U, signed V) {
    return s.qry(P, U, Q, V);
}

Compilation message

game.cpp: In member function 'long long int Teapy::qry(long long int, long long int)':
game.cpp:104:15: warning: unused variable 'tmp2' [-Wunused-variable]
  104 |         Node* tmp2;
      |               ^~~~
/usr/bin/ld: /tmp/ccI7E4lh.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