oj.uz

Submission #258455

# Submission time Handle Problem Language Result Execution time Memory
258455 2020-08-06T00:11:59 Z sandoval Game (IOI13_game) C++11
63 / 100
 2227 ms 35520 KB 
#include <bits/stdc++.h>
#include "game.h"

using namespace std;
using ii = pair<int,int>;
using ll = long long;

constexpr int MAXN = 5 + 2000;

ll gcd(ll a, ll b) {
  return b ? gcd(b, a%b) : a;
}

struct segtree {
#define m ((s+e)/2)
struct Node {
  ll val;
  Node* l, *r;
  Node() : val(0), l(nullptr), r(nullptr) {}
};
Node* root = new Node();
segtree() = default;
ll query(int s, int e, Node* curr, int l, int r) {
  if (l > r || curr == nullptr) return 0;
  if (s == l && e == r) return curr->val;
  return gcd(query(s, m, curr->l, l, min(m,r)), query(1+m, e, curr->r, max(1+m,l), r));
}
void update(int s, int e, Node* curr, int l, int r, ll add) {
  if (l > r) return;
  if (s == l && e == r) {
    curr->val = add;
  } else {
    if (curr->l == nullptr) curr->l = new Node();
    if (curr->r == nullptr) curr->r = new Node();
    update(s, m, curr->l, l, min(m,r), add);
    update(1+m, e, curr->r, max(1+m,l), r, add);
    curr->val = gcd(curr->l->val, curr->r->val);
  }
}};

namespace input {int R,C;}

namespace stree2d {
segtree t[4*MAXN];
ll query(int s, int e, int p, int l, int r, int sy, int ey) {
  if (l > r) return 0;
  if (s == l && e == r) return t[p].query(1, input::C, t[p].root, sy, ey);
  ll le = query(s, m, 2*p, l, min(m,r), sy, ey);
  ll ri = query(1+m, e, 1+2*p, max(1+m,l), r, sy, ey);
  return gcd(le,ri);
}
void update(int s, int e, int p, int l, int r, int sy, int ey, ll add) {
  if (l > r) return;
  if (s == l && e == r) {
    t[p].update(1, input::C, t[p].root, sy, ey, add);
  } else {
    update(s, m, 2*p, l, min(m,r), sy, ey, add);
    update(1+m, e, 1+2*p, max(1+m,l), r, sy, ey, add);
    ll newval = gcd(t[2*p].query(1, input::C, t[2*p].root, sy, ey),
           t[1+2*p].query(1, input::C, t[1+2*p].root, sy, ey));
    t[p].update(1, input::C, t[p].root, sy, sy, newval);
  }
}}

int subtask=-1;
void init(int R, int C) {
  if (R <= 10 && C <= 100000) { // subtask 2.
    subtask = 2;
  } else { // subtask 1 & 3.
    subtask = 3;
  }
  input::R = R;
  input::C = C;
}

segtree s2[11];

void update(int P, int Q, long long K) {
  if (subtask == -1) return;
  ++P; ++Q;
  if (subtask == 2) { // 10 segment trees.
    s2[P].update(1, input::C, s2[P].root, Q, Q, K);
  } else { // un solo segtree 2d.
    assert(subtask == 3);
    stree2d::update(1, input::R, 1, P, P, Q, Q, K);
  }
}

long long calculate(int P, int Q, int U, int V) {
  ++P; ++Q; ++U; ++V;
  if (subtask == 2) {
    long long ans = 0;
    for (int i = P; i <= U; ++i) {
      ans = gcd(ans, s2[i].query(1, input::C, s2[i].root, Q, V));
    }
    return ans;
  } else {
    assert(subtask == 3);
    assert(P >= 1 && P <= input::R);
    assert(U >= 1 && U <= input::R);
    assert(P <= U);

    assert(Q >= 1 && Q <= input::C);
    assert(V >= 1 && V <= input::C);
    assert(Q <= V);
    return stree2d::query(1, input::R, 1, P, U, Q, V);
  }
  return 0LL;
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 735 ms 13304 KB Output is correct
5 Correct 505 ms 13048 KB Output is correct
6 Correct 631 ms 10744 KB Output is correct
7 Correct 687 ms 10364 KB Output is correct
8 Correct 492 ms 8824 KB Output is correct
9 Correct 695 ms 10488 KB Output is correct
10 Correct 663 ms 10188 KB Output is correct
11 Correct 1 ms 640 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 2 ms 768 KB Output is correct
3 Correct 1 ms 768 KB Output is correct
4 Correct 1 ms 640 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 1 ms 640 KB Output is correct
12 Correct 888 ms 27128 KB Output is correct
13 Correct 1351 ms 13008 KB Output is correct
14 Correct 356 ms 6264 KB Output is correct
15 Correct 1575 ms 17604 KB Output is correct
16 Correct 313 ms 33864 KB Output is correct
17 Correct 1144 ms 23268 KB Output is correct
18 Correct 1854 ms 35216 KB Output is correct
19 Correct 1754 ms 35392 KB Output is correct
20 Correct 1523 ms 34808 KB Output is correct
21 Correct 1 ms 640 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 2 ms 768 KB Output is correct
3 Correct 1 ms 768 KB Output is correct
4 Correct 1 ms 640 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 1 ms 640 KB Output is correct
12 Correct 743 ms 13224 KB Output is correct
13 Correct 526 ms 13052 KB Output is correct
14 Correct 631 ms 10612 KB Output is correct
15 Correct 738 ms 10360 KB Output is correct
16 Correct 513 ms 9000 KB Output is correct
17 Correct 677 ms 10636 KB Output is correct
18 Correct 760 ms 10104 KB Output is correct
19 Correct 929 ms 26872 KB Output is correct
20 Correct 1342 ms 12856 KB Output is correct
21 Correct 370 ms 6392 KB Output is correct
22 Correct 1617 ms 17612 KB Output is correct
23 Correct 298 ms 33904 KB Output is correct
24 Correct 1097 ms 23288 KB Output is correct
25 Correct 1900 ms 35256 KB Output is correct
26 Correct 1838 ms 35400 KB Output is correct
27 Correct 1475 ms 34808 KB Output is correct
28 Runtime error 1 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 2 ms 768 KB Output is correct
3 Correct 2 ms 768 KB Output is correct
4 Correct 1 ms 640 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 2 ms 768 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 1 ms 640 KB Output is correct
12 Correct 746 ms 13196 KB Output is correct
13 Correct 497 ms 13052 KB Output is correct
14 Correct 614 ms 10616 KB Output is correct
15 Correct 739 ms 10488 KB Output is correct
16 Correct 494 ms 8952 KB Output is correct
17 Correct 740 ms 10560 KB Output is correct
18 Correct 654 ms 10256 KB Output is correct
19 Correct 937 ms 27000 KB Output is correct
20 Correct 1333 ms 13048 KB Output is correct
21 Correct 360 ms 6136 KB Output is correct
22 Correct 1557 ms 17556 KB Output is correct
23 Correct 333 ms 33784 KB Output is correct
24 Correct 996 ms 23288 KB Output is correct
25 Correct 2227 ms 35456 KB Output is correct
26 Correct 1708 ms 35520 KB Output is correct
27 Correct 1674 ms 34936 KB Output is correct
28 Runtime error 2 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -