oj.uz

Submission #962805

# Submission time Handle Problem Language Result Execution time Memory
962805 2024-04-14T08:27:58 Z danikoynov Game (IOI13_game) C++14
100 / 100
 5496 ms 111136 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 1 ms 376 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 864 ms 24376 KB Output is correct
5 Correct 541 ms 24792 KB Output is correct
6 Correct 1607 ms 21508 KB Output is correct
7 Correct 1692 ms 21308 KB Output is correct
8 Correct 1016 ms 11668 KB Output is correct
9 Correct 1696 ms 21284 KB Output is correct
10 Correct 1384 ms 21088 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1035 ms 24620 KB Output is correct
13 Correct 2186 ms 21040 KB Output is correct
14 Correct 903 ms 20336 KB Output is correct
15 Correct 2359 ms 21216 KB Output is correct
16 Correct 868 ms 21500 KB Output is correct
17 Correct 1747 ms 11508 KB Output is correct
18 Correct 3234 ms 22012 KB Output is correct
19 Correct 2768 ms 22120 KB Output is correct
20 Correct 2648 ms 21088 KB Output is correct
21 Correct 0 ms 344 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 877 ms 24448 KB Output is correct
13 Correct 535 ms 24624 KB Output is correct
14 Correct 1538 ms 21744 KB Output is correct
15 Correct 1664 ms 21516 KB Output is correct
16 Correct 1046 ms 11560 KB Output is correct
17 Correct 1627 ms 21188 KB Output is correct
18 Correct 1364 ms 21012 KB Output is correct
19 Correct 1000 ms 24456 KB Output is correct
20 Correct 2237 ms 21112 KB Output is correct
21 Correct 867 ms 20232 KB Output is correct
22 Correct 2386 ms 21420 KB Output is correct
23 Correct 888 ms 21584 KB Output is correct
24 Correct 1735 ms 11496 KB Output is correct
25 Correct 3193 ms 22016 KB Output is correct
26 Correct 2954 ms 21744 KB Output is correct
27 Correct 2725 ms 21448 KB Output is correct
28 Correct 817 ms 57708 KB Output is correct
29 Correct 1381 ms 60308 KB Output is correct
30 Correct 3299 ms 42368 KB Output is correct
31 Correct 2764 ms 38960 KB Output is correct
32 Correct 844 ms 29432 KB Output is correct
33 Correct 1070 ms 29564 KB Output is correct
34 Correct 1251 ms 54084 KB Output is correct
35 Correct 1866 ms 35016 KB Output is correct
36 Correct 3495 ms 58120 KB Output is correct
37 Correct 2824 ms 58388 KB Output is correct
38 Correct 2862 ms 57972 KB Output is correct
39 Correct 2364 ms 47540 KB Output is correct
40 Correct 1 ms 440 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 861 ms 24560 KB Output is correct
13 Correct 547 ms 25100 KB Output is correct
14 Correct 1541 ms 21324 KB Output is correct
15 Correct 1694 ms 21188 KB Output is correct
16 Correct 1022 ms 11744 KB Output is correct
17 Correct 1660 ms 21308 KB Output is correct
18 Correct 1471 ms 21080 KB Output is correct
19 Correct 1048 ms 24716 KB Output is correct
20 Correct 2319 ms 21072 KB Output is correct
21 Correct 860 ms 20308 KB Output is correct
22 Correct 2436 ms 21220 KB Output is correct
23 Correct 856 ms 21512 KB Output is correct
24 Correct 1791 ms 11500 KB Output is correct
25 Correct 3331 ms 21604 KB Output is correct
26 Correct 2916 ms 21832 KB Output is correct
27 Correct 2820 ms 21468 KB Output is correct
28 Correct 913 ms 57460 KB Output is correct
29 Correct 1577 ms 60372 KB Output is correct
30 Correct 3513 ms 42344 KB Output is correct
31 Correct 3045 ms 38872 KB Output is correct
32 Correct 858 ms 29524 KB Output is correct
33 Correct 1115 ms 29684 KB Output is correct
34 Correct 1241 ms 53964 KB Output is correct
35 Correct 1918 ms 34920 KB Output is correct
36 Correct 3442 ms 58140 KB Output is correct
37 Correct 2820 ms 58400 KB Output is correct
38 Correct 2888 ms 58140 KB Output is correct
39 Correct 1266 ms 109312 KB Output is correct
40 Correct 2486 ms 111136 KB Output is correct
41 Correct 5496 ms 82128 KB Output is correct
42 Correct 4869 ms 74500 KB Output is correct
43 Correct 1444 ms 106052 KB Output is correct
44 Correct 1590 ms 53164 KB Output is correct
45 Correct 2327 ms 47324 KB Output is correct
46 Correct 4307 ms 110384 KB Output is correct
47 Correct 4321 ms 110128 KB Output is correct
48 Correct 4280 ms 109984 KB Output is correct
49 Correct 0 ms 348 KB Output is correct