Submission #531650

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

game

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 9;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct treapNode {
  treapNode* l;
  treapNode* r;
  int key, prior, val, gcd;
};

using ptr = treapNode*;
using pt = pair<ptr, ptr>;
ptr NIL = new treapNode{nullptr, nullptr, 0, -1, 0, 0};

void updateNode(ptr x) {
  if (x != NIL) {
    x->gcd = __gcd(__gcd(x->l->gcd, x->val), x->r->gcd);
  }
}

pt split(ptr x, int k) {
  if (x == NIL) {
    return {NIL, NIL};
  }
  if (k < x->key) {
    pt p = split(x->l, k);
    x->l = p.second;
    updateNode(x);
    return {p.first, x};
  }
  pt p = split(x->r, k);
  x->r = p.first;
  updateNode(x);
  return {x, p.second};
}

ptr join(ptr x, ptr y) {
  if (x == NIL) {
    return y;
  }
  if (y == NIL) {
    return x;
  }
  if (y->prior < x->prior) {
    x->r = join(x->r, y);
    updateNode(x);
    return x;
  }
  y->l = join(x, y->l);
  updateNode(y);
  return y;
}

bool check(ptr x, int k, int v) {
  if (!x) {
    return false;
  }
  if (x->key == k) {
    x->gcd = v;
    updateNode(x);
    return true;
  }
  if (k < x->key) {
    bool ret = check(x->l, k, v);
    updateNode(x);
    return ret;
  } else {
    bool ret = check(x->r, k, v);
    updateNode(x);
    return ret;
  }
}

ptr ins(ptr x, int k, int v) {
  if (check(x, k, v)) {
    return x;
  }
  pt p = split(x, k);
  ptr newNode = new treapNode{NIL, NIL, k, rng() % mod, v, v};
  return join(join(p.first, newNode), p.second);
}

int queryY(ptr x, int st, int dr) {
  pt p1 = split(x, st - 1);
  pt p2 = split(p1.second, dr - st + 1);
  int ans = p2.first->gcd;
  p1.second = join(p2.first, p2.second);
  x = join(p1.first, p1.second);
  return ans;
}

struct sgtNode {
  ptr root;
  sgtNode* l;
  sgtNode* r;

  sgtNode() {

  }
};

void update(sgtNode* x, int lx, int rx, int X, int Y, int v) {
  if (lx == rx) {

    return;
  }
  int mid = (lx + rx) / 2;
  if (X <= mid) {

    update(x->l, lx, mid, X, Y, v);

  } else {

    update(x->r, mid + 1, rx, X, Y, v);

  }
}

int queryX(sgtNode* x, int lx, int rx, int x1, int x2, int y1, int y2) {
  if (x1 <= lx && rx <= x2) {

  }
  int mid = (lx + rx) / 2, ans = 0;
  if (x1 <= mid) {

    ans = __gcd(ans, queryX(x->l, lx, mid, x1, x2, y1, y2));

  }
  if (mid < x2) {

    ans = __gcd(ans, queryX(x->r, mid + 1, rx, x1, x2, y1, y2));

  }
  return ans;
}

void testCase() {

}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

Compilation message (stderr)

game.cpp: In function 'treapNode* ins(ptr, int, int)':
game.cpp:82:50: warning: narrowing conversion of '(rng.std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::operator()() % ((std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type)((int)mod)))' from 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   82 |   ptr newNode = new treapNode{NIL, NIL, k, rng() % mod, v, v};
      |                                            ~~~~~~^~~~~
/usr/bin/ld: /tmp/cct29yBG.o: in function `main':
game.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccEWC3CG.o:grader.c:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccEWC3CG.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