Submission #962755

#	Time	Username	Problem	Language	Result	Execution time	Memory
962755		danikoynov	Game (IOI13_game)	C++14	10 / 100	13086 ms	18852 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 int maxc = 1e9 + 10;

struct vertex
{
     vertex *lc, *rc;
     set < pair < int, ll > > values;

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

void remove_from_vertex(vertex *root, pair < int, ll > val)
{
     root -> values.erase(val);
}
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;
     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:65:6: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   65 |      if (left == right)
      |      ^~
game.cpp:68:11: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   68 |           make_kids(root);
      |           ^~~~~~~~~

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