Submission #531884

#	Time	Username	Problem	Language	Result	Execution time	Memory
531884		Alex_tz307	Game (IOI13_game)	C++17	100 / 100	6386 ms	47336 KiB

game

#include <bits/stdc++.h>
#include "game.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;
  int64_t val, gcd;
};
 
using ptr = treapNode*;
using pt = pair<ptr, ptr>;
ptr NIL = new treapNode{nullptr, nullptr, 0, -1, 0, 0};
 
int64_t gcd2(int64_t X, int64_t Y) {
  int64_t tmp;
  while (X != Y && Y != 0) {
    tmp = X;
    X = Y;
    Y = tmp % Y;
  }
  return X;
}
 
void updateNode(ptr &x) {
  if (x != NIL) {
    x->gcd = gcd2(gcd2(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, int64_t v) {
  if (x == NIL) {
    return false;
  }
  if (x->key == k) {
    x->val = 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, int64_t 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);
}
 
int64_t queryY(ptr &x, int st, int dr) {
  pt p1 = split(x, st - 1);
  pt p2 = split(p1.second, dr);
  int64_t 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() : root(NIL), l(nullptr), r(nullptr) {}
} *root;
 
void update(sgtNode* &x, int lx, int rx, int X, int Y, int64_t v) {
  if (!x) {
    x = new sgtNode();
  }
  if (lx == rx) {
    x->root = ins(x->root, Y, v);
    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);
  }
  int64_t gcd = 0;
  if (x->l) {
    gcd = queryY(x->l->root, Y, Y);
  }
  if (x->r) {
    gcd = gcd2(gcd, queryY(x->r->root, Y, Y));
  }
  x->root = ins(x->root, Y, gcd);
}
 
int64_t queryX(sgtNode* &x, int lx, int rx, int x1, int x2, int y1, int y2) {
  if (!x) {
    return 0;
  }
  if (x1 <= lx && rx <= x2) {
    return queryY(x->root, y1, y2);
  }
  int mid = (lx + rx) / 2;
  int64_t ans = 0;
  if (x1 <= mid) {
    ans = gcd2(ans, queryX(x->l, lx, mid, x1, x2, y1, y2));
  }
  if (mid < x2) {
    ans = gcd2(ans, queryX(x->r, mid + 1, rx, x1, x2, y1, y2));
  }
  return ans;
}
 
int N;
 
void init(int R, int C) {
  N = R;
}
 
void update(int P, int Q, long long K) {
  update(root, 0, N - 1, P, Q, K);
}
 
long long calculate(int P, int Q, int U, int V) {
  return queryX(root, 0, N - 1, P, U, Q, V);
}

Compilation message (stderr)

game.cpp: In function 'treapNode* ins(treapNode*&, int, int64_t)':
game.cpp:94: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]
   94 |   ptr newNode = new treapNode{NIL, NIL, k, rng() % mod, v, v};
      |                                            ~~~~~~^~~~~

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