Submission #1268107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268107		angelolan	Game (IOI13_game)	C++20	Compilation error	0 ms	0 KiB

game

#include <bits/stdc++.h>
using namespace std;
// Pura Gente del Coach Moy y la Alexbriza

using ll = long long;

struct TreapNode {
  TreapNode *l = 0, *r = 0;
  int i, j, y;
  ll val, g;
  TreapNode(int i, int j, ll val) : i(i), j(j), y(rand()), val(val), g(val) {}
  void recalc();
};

ll getGcd(TreapNode* n) { return n ? n->g : 0; }

void TreapNode::recalc() { g = gcd(val, gcd(getGcd(l), getGcd(r))); }

pair<TreapNode*, TreapNode*> split(TreapNode* n, int i, int j) {
  if (!n) return {};
  if (make_pair(n->j, n->i) >= make_pair(j, i)) {
    auto [L,R] = split(n->l, i, j);
    n->l = R;
    n->recalc();
    return {L, n};
  } else {
    auto [L,R] = split(n->r, i, j);
    n->r = L;
    n->recalc();
    return {n, R};
  }
}

TreapNode* merge(TreapNode* l, TreapNode* r) {
  if (!l) return r;
  if (!r) return l;
  if (l->y > r->y) {
    l->r = merge(l->r, r);
    return l->recalc(), l;
  } else {
    r->l = merge(l, r->l);
    return r->recalc(), r;
  }
}

void setTreap(TreapNode*& n, int i, int j, ll x) {
  auto [L1, R1] = split(n, i, j);
  auto [L2, R2] = split(R1, i + 1, j);
  n = merge(L1, merge(new TreapNode(i, j, x), R2));
}

ll queryTreap(TreapNode* n, int j1, int j2) {
  auto [L1, R1] = split(n, 0, j1);
  auto [L2, R2] = split(R1, 0, j2);
  ll g = getGcd(L2);
  n = merge(L1, merge(L2, R2));
  return g;
}

struct STree {
  struct Node {
    TreapNode* treapRoot = nullptr;
    int l = -1, r = -1;
  };
  
  int n;
  vector<Node> st = vector<Node>(1);
  
  STree(int n) : n(n) {}

  int set(int v, int tl, int tr, int i, int j, ll val) {
    if (v == -1) {
      v = int(st.size());
      st.emplace_back();
    }
    setTreap(st[v].treapRoot, i, j, val);
    if (tl + 1 == tr) return v;
    int tm = (tl + tr) / 2;
    i < tm ? st[v].l = set(st[v].l, tl, tm, i, j, val) : st[v].r = set(st[v].r, tm, tr, i, j, val);
    return v;
  }

  ll query(int v, int tl, int tr, int i1, int i2, int j1, int j2) {
    if (v == -1) return 0;
    if (i1 <= tl && tr <= i2) return queryTreap(st[v].treapRoot, j1, j2);
    int tm = (tl + tr) / 2;
    if (i1 < tm && i2 > tm) {
      return gcd(query(st[v].l, tl, tm, i1, i2, j1, j2), query(st[v].r, tm, tr, i1, i2, j1, j2));
    } else if (i1 < tm) {
      return query(st[v].l, tl, tm, i1, i2, j1, j2);
    }
    return query(st[v].r, tm, tr, i1, i2, j1, j2);
  }

  void set(int i, int j, ll val) { set(0, 0, n, i, j, val); }
  ll query(int i1, int i2, int j1, int j2) { return query(0, 0, n, i1, i2, j1, j2); }
};

int main() {
  cin.tie(0)->sync_with_stdio(0);

  int N, M, Q;
  cin >> N >> M >> Q;

  STree st(N);
  while (Q--) {
    int op;
    cin >> op;

    if (op == 1) {
      int X, Y;
      ll C;
      cin >> X >> Y >> C;
      st.set(X, Y, C);
    } else {
      int A, B, X, Y;
      cin >> A >> B >> X >> Y;
      cout << st.query(A, X + 1, B, Y + 1) << '\n';
    }
  }
}

Compilation message (stderr)

/usr/bin/ld: /tmp/cc70IJD7.o: in function `main':
grader.c:(.text.startup+0x0): multiple definition of `main'; /tmp/cc6tAjfF.o:game.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc70IJD7.o: in function `main':
grader.c:(.text.startup+0x6a): undefined reference to `init'
/usr/bin/ld: grader.c:(.text.startup+0xcc): undefined reference to `calculate'
/usr/bin/ld: grader.c:(.text.startup+0x136): undefined reference to `update'
collect2: error: ld returned 1 exit status