oj.uz

Submission #258459

# Submission time Handle Problem Language Result Execution time Memory
258459 2020-08-06T00:20:51 Z sandoval Game (IOI13_game) C++11
63 / 100
 1736 ms 256004 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;
}

#define m ((s+e)/2)
struct segtree {
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 {
struct Node2d {
  segtree t;
  Node2d* l, *r;
  Node2d() : l(nullptr), r(nullptr) {}
};
Node2d* root = new Node2d();
ll query(int s, int e, Node2d* curr, int l, int r, int sy, int ey) {
  if (l > r || curr == nullptr) return 0;
  if (s == l && e == r) return curr->t.query(1, input::C, curr->t.root, sy, ey);
  ll le = query(s, m, curr->l, l, min(m,r), sy, ey);
  ll ri = query(1+m, e, curr->r, max(1+m,l), r, sy, ey);
  return gcd(le,ri);
}
void update(int s, int e, Node2d* curr, int l, int r, int sy, int ey, ll add) {
  if (l > r) return;
  if (s == l && e == r) {
    curr->t.update(1, input::C, curr->t.root, sy, ey, add);
  } else {
    if (curr->l == nullptr) curr->l = new Node2d();
    if (curr->r == nullptr) curr->r = new Node2d();

    update(s, m, curr->l, l, min(m,r), sy, ey, add);
    update(1+m, e, curr->r, max(1+m,l), r, sy, ey, add);
    ll newval = gcd(curr->l->t.query(1, input::C, curr->l->t.root, sy, ey),
           curr->r->t.query(1, input::C, curr->r->t.root, sy, ey));
    curr->t.update(1, input::C, curr->t.root, sy, sy, newval);
  }
}}

void init(int R, int C) {
  input::R = R;
  input::C = C;
}

void update(int P, int Q, long long K) {
  ++P; ++Q;
  stree2d::update(1, input::R, stree2d::root, P, P, Q, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
  ++P; ++Q; ++U; ++V;
  return stree2d::query(1, input::R, stree2d::root, P, U, Q, V);
}

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 256 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 627 ms 20056 KB Output is correct
5 Correct 437 ms 20360 KB Output is correct
6 Correct 554 ms 17412 KB Output is correct
7 Correct 616 ms 17144 KB Output is correct
8 Correct 429 ms 11896 KB Output is correct
9 Correct 600 ms 17272 KB Output is correct
10 Correct 572 ms 16760 KB Output is correct
11 Correct 0 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 890 ms 24244 KB Output is correct
13 Correct 1330 ms 10488 KB Output is correct
14 Correct 348 ms 2680 KB Output is correct
15 Correct 1524 ms 14392 KB Output is correct
16 Correct 291 ms 30968 KB Output is correct
17 Correct 1037 ms 19856 KB Output is correct
18 Correct 1720 ms 31636 KB Output is correct
19 Correct 1466 ms 31512 KB Output is correct
20 Correct 1413 ms 30812 KB Output is correct
21 Correct 1 ms 256 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 623 ms 19832 KB Output is correct
13 Correct 430 ms 20216 KB Output is correct
14 Correct 575 ms 17144 KB Output is correct
15 Correct 635 ms 16888 KB Output is correct
16 Correct 438 ms 11640 KB Output is correct
17 Correct 606 ms 17016 KB Output is correct
18 Correct 566 ms 16532 KB Output is correct
19 Correct 890 ms 23940 KB Output is correct
20 Correct 1324 ms 10232 KB Output is correct
21 Correct 349 ms 2496 KB Output is correct
22 Correct 1522 ms 14448 KB Output is correct
23 Correct 303 ms 31096 KB Output is correct
24 Correct 993 ms 19576 KB Output is correct
25 Correct 1730 ms 31352 KB Output is correct
26 Correct 1440 ms 31224 KB Output is correct
27 Correct 1409 ms 30468 KB Output is correct
28 Runtime error 685 ms 256004 KB Execution killed with signal 9 (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 256 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 601 ms 20080 KB Output is correct
13 Correct 433 ms 20512 KB Output is correct
14 Correct 553 ms 17528 KB Output is correct
15 Correct 630 ms 17388 KB Output is correct
16 Correct 408 ms 11896 KB Output is correct
17 Correct 602 ms 17276 KB Output is correct
18 Correct 620 ms 16812 KB Output is correct
19 Correct 925 ms 24184 KB Output is correct
20 Correct 1302 ms 10488 KB Output is correct
21 Correct 353 ms 2708 KB Output is correct
22 Correct 1515 ms 14684 KB Output is correct
23 Correct 322 ms 31352 KB Output is correct
24 Correct 1034 ms 20088 KB Output is correct
25 Correct 1736 ms 31464 KB Output is correct
26 Correct 1493 ms 31568 KB Output is correct
27 Correct 1498 ms 30844 KB Output is correct
28 Runtime error 654 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -