oj.uz

Submission #962755

# Submission time Handle Problem Language Result Execution time Memory
962755 2024-04-14T07:55:21 Z danikoynov Game (IOI13_game) C++14
10 / 100
 13000 ms 18852 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 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

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

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

Subtask #2
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 0 ms 348 KB Output is correct
4 Execution timed out 13059 ms 18852 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 856 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 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 1 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 6879 ms 11292 KB Output is correct
13 Correct 7725 ms 6284 KB Output is correct
14 Incorrect 712 ms 1872 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 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 1 ms 604 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Execution timed out 13086 ms 18424 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 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 1 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 Execution timed out 13014 ms 18524 KB Time limit exceeded
13 Halted 0 ms 0 KB -