Submission #962805

#	Time	Username	Problem	Language	Result	Execution time	Memory
962805		danikoynov	게임 (IOI13_game)	C++14	100 / 100	5496 ms	111136 KiB

game

#include "game.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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;
}


void init(int R, int C)
{
    /* ... */
}

const ll inf = 1e18;
const int maxc = 1e9 + 10;

vector < pair < int, ll > > keys;

mt19937 rng;
struct node
{
     int priority, sz;
     ll sub;
     pair < int, ll > key;
     node *lc, *rc;

     node(pair < int, ll > _key = {0, 0})
     {
          key = _key;
          sub = key.second;
          priority = rng();
          sz = 1;
          lc = rc = NULL;
     }

     void con()
     {
          sz = 1;
          sub = key.second;
          if (lc != NULL)
          {
               sz += lc -> sz;
               sub = gcd2(sub, lc -> sub);
          }

          if (rc != NULL)
          {
               sz += rc -> sz;
               sub = gcd2(sub, rc -> sub);
          }
     }

     void print()
     {
          if (lc) lc -> print();
          cout << key.first << " " << key.second << endl;
          if (rc) rc -> print();
     }

     void get_keys()
     {
          if (lc) lc -> get_keys();
          keys.push_back(key);
          if (rc) rc -> get_keys();
     }
};


struct Treap
{
     node *root = NULL;

     void SplitKey(node *T, node *&L, node *&R, pair < int, ll > splitter)
     {
          if (T == NULL)
          {
               L = NULL;
               R = NULL;
               return;
          }

          if (T -> key < splitter)
          {
               L = T;
               SplitKey(T -> rc, L -> rc, R, splitter);
          }
          else
          {
               R = T;
               SplitKey(T -> lc, L, R -> lc, splitter);
          }

          T -> con();
     }

     void SplitSize(node *T, node *&L, node *&R, int tsz)
     {
          if (T == NULL)
          {
               L = NULL;
               R = NULL;
               return;
          }

          int csz = 1;
          if (T -> lc) csz += T -> lc -> sz;
          if (tsz >= csz)
          {
               L = T;
               SplitSize(T -> rc, L -> rc, R, tsz - csz);
          }
          else
          {
               R = T;
               SplitSize(T -> lc, L, R -> lc, tsz);
          }

          T -> con();

     }

     void Merge(node *&T, node *L, node *R)
     {
          if (L == NULL)
          {
               T = R;
               return;
          }
          if (R == NULL)
          {
               T = L;
               return;
          }

          if (L -> priority > R -> priority)
          {
               T = L;
               Merge(T -> rc, L -> rc, R);
          }
          else
          {
               T = R;
               Merge(T -> lc, L, R -> lc);
          }

          T -> con();
     }

     void add(pair < int, ll > cur)
     {
          node *L = NULL, *M = new node(cur), *R = NULL;
          SplitKey(root, L, R, cur);
          Merge(L, L, M);
          Merge(root, L, R);

     }

     void rem(pair < int, ll > cur)
     {
          node *L = NULL, *R = NULL, *M = NULL;
          SplitKey(root, L, R, cur);
          SplitSize(R, M, R, 1);
          Merge(root, L, R);
     }


     ll query(int l, int r)
     {
          node *L, *M, *R;
          SplitKey(root, L, R, {l, -inf});
          SplitKey(R, M, R, {r + 1, -inf});
          ll res = 0;
          if (M != NULL) res = M -> sub;
          Merge(R, M, R);
          Merge(root, L, R);
          return res;
     }

     void print()
     {
          cout << "My Treap" << endl;
          root -> print();
          cout << "------------" << endl;
     }

     void get_keys()
     {
          keys.clear();
          if (root)
          root -> get_keys();
     }

     //void get_key()
};
struct vertex
{
     vertex *lc, *rc;
     multiset < pair < int, ll > > values;
     Treap buzz;
     vertex()
     {
          lc = rc = NULL;
          values.clear();
     }
};

vertex *tree = new vertex();

void make_kids(vertex *root)
{
     if (root -> lc == NULL)
          root -> lc = new vertex();
     if (root -> rc == NULL)
          root -> rc = new vertex();
}

void add_to_vertex(vertex *root, pair < int, ll > val)
{
     //root -> values.insert(val);
     root -> buzz.add(val);

     /**     root -> buzz.get_keys();
     int to = 0;
     for (pair < int, ll > cur : root -> values)
     {
          assert(cur == keys[to ++]);
     }

      int sz = 0;
     if (root -> buzz.root != NULL) sz = root -> buzz.root -> sz;
     assert(sz == root -> values.size());*/
     //assert(root -> buzz.root -> sz == root -> values.size());
}

void remove_from_vertex(vertex *root, pair < int, ll > val)
{
     //cout << "remove " << " " << val.first << " " << val.second << endl;
     //root -> buzz.print();

     /**cout << "my set" << endl;
     for (pair < int, ll > cur : root ->values)
          cout << cur.first << " " << cur.second << endl;*/
     root -> buzz.rem(val);
     //root -> values.erase(root -> values.find(val));
     /**cout << "after" << endl;
     root -> buzz.print();
     cout << "the set" << endl;
          for (pair < int, ll > cur : root ->values)
          cout << cur.first << " " << cur.second << endl;*/

     /**root -> buzz.get_keys();
     int to = 0;
     for (pair < int, ll > cur : root -> values)
     {
          assert(cur == keys[to ++]);
     }
     int sz = 0;
     if (root -> buzz.root != NULL) sz = root -> buzz.root -> sz;
     assert(sz == root -> values.size());*/
}
void add_val(vertex *root, int left, int right, int pivot, pair < int, ll > val)
{
     ///cout << "add val " << left << " " << right << " " << pivot << endl;
     add_to_vertex(root, val);
     ///cout << "fine" << endl;
     if (left == right)
          return;

          make_kids(root);
     int mid = (left + right) / 2;

     if (pivot <= mid)
     add_val(root -> lc, left, mid, pivot, val);
     else
     add_val(root -> rc, mid + 1, right, pivot, val);
}

void remove_val(vertex *root, int left, int right, int pivot, pair < int, ll > val)
{
     remove_from_vertex(root, val);
     if (left == right)
          return;

          ///make_kids(root);
     int mid = (left + right) / 2;

     if (pivot <= mid)
     remove_val(root -> lc, left, mid, pivot, val);
     else
     remove_val(root -> rc, mid + 1, right, pivot, val);
}
map < pair < int, int >, ll > board;
void update(int P, int Q, long long K)
{
     //cout << "update " << P << " " << Q << " " << K << endl;
     if (board.count({P, Q}))
          remove_val(tree, 0, maxc, P, {Q, board[{P, Q}]});
       //   cout << "Survive" << endl;
     board[{P, Q}] = K;
     add_val(tree, 0, maxc, P, {Q, K});
     ///cout << "Fuck" << endl;
    /* ... */
}

ll query_vertex(vertex *root, int dw, int up)
{
     //ll res = 0;
     ll res = root -> buzz.query(dw, up);
     /**for (pair < int, ll > cur : root -> values)
     {
          if (cur.first >= dw && cur.first <= up)
               res = gcd2(res, cur.second);
     }*/
     return res;
}
ll query(vertex *root, int left, int right, int qleft, int qright, int kmin, int kmax)
{
     if (root == NULL || left > qright || right < qleft)
          return 0;

     if (left >= qleft && right <= qright)
     {
          return query_vertex(root, kmin, kmax);
     }

     int mid = (left + right) / 2;
     return gcd2(query(root -> lc, left, mid, qleft, qright, kmin, kmax),
                 query(root -> rc, mid + 1, right, qleft, qright, kmin, kmax));
}
long long calculate(int P, int Q, int U, int V)
{
     /**map < pair < int, int >, ll > :: iterator it;
     ll res = 0;
     for (it = board.begin(); it != board.end(); it ++)
     {
          pair < int, int > cor = it -> first;
          if (cor.first >= P && cor.first <= U &&
              cor.second >= Q && cor.second <= V)
          {
               res = __gcd(res, it -> second);
          }
     }*/
    /* ... */
    return query(tree, 0, maxc, P, U, Q, V);
}

Compilation message (stderr)

game.cpp: In function 'void add_val(vertex*, int, int, int, std::pair<int, long long int>)':
game.cpp:279:6: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  279 |      if (left == right)
      |      ^~
game.cpp:282:11: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  282 |           make_kids(root);
      |           ^~~~~~~~~

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