oj.uz

Submission #102993

# Submission time Handle Problem Language Result Execution time Memory
102993 2019-03-28T11:26:01 Z wxh010910 Game (IOI13_game) C++17
100 / 100
 7093 ms 95480 KB 
#include <bits/stdc++.h>
#include "game.h"

using namespace std;

class hor {
 public:
  hor* l;
  hor* r;
  int y;
  long long g;

  hor(int y = -1): y(y) {
    l = r = NULL;
    g = 0;
  }
};

class ver {
 public:
  ver* l;
  ver* r;
  hor* h;

  ver() {
    l = r = NULL;
    h = NULL;
  }
};

ver* root;
int n, m;

inline long long gcd(long long a, long long b) {
  if (!a || !b) {
    return a ^ b;
  } else {
    int shift = __builtin_ctzll(a | b);
    b >>= __builtin_ctzll(b);
    while (a) {
      a >>= __builtin_ctzll(a);
      if (a < b) {
        swap(a, b);
      }
      a -= b;
    }
    return b << shift;
  }
}

long long query(hor* root, int l, int r, int yl, int yr) {
  if (root == NULL) {
    return 0;
  }
  if (root->y != -1) {
    return yl <= root->y && root->y <= yr ? root->g : 0;
  }
  if (yl <= l && r <= yr) {
    return root->g;
  } else {
    int mid = (l + r) >> 1;
    long long ans = 0;
    if (yl <= mid) {
      ans = gcd(ans, query(root->l, l, mid, yl, yr));
    }
    if (yr > mid) {
      ans = gcd(ans, query(root->r, mid + 1, r, yl, yr));
    }
    return ans;
  }
}

long long query(ver* root, int l, int r, int xl, int xr, int yl, int yr) {
  if (root == NULL) {
    return 0;
  }
  if (xl <= l && r <= xr) {
    return query(root->h, 0, m - 1, yl, yr);
  } else {
    int mid = (l + r) >> 1;
    long long ans = 0;
    if (xl <= mid) {
      ans = gcd(ans, query(root->l, l, mid, xl, xr, yl, yr));
    }
    if (xr > mid) {
      ans = gcd(ans, query(root->r, mid + 1, r, xl, xr, yl, yr));
    }
    return ans;
  }
}

void modify(hor* root, int l, int r, int y, long long g) {
  int mid = (l + r) >> 1;
  if (root->y != -1) {
    if (root->y == y) {
      root->g = g;
      return;
    } else {
      if (root->y <= mid) {
        root->l = new hor(root->y);
        root->l->g = root->g;
      } else {
        root->r = new hor(root->y);
        root->r->g = root->g;
      }
      root->y = -1;
    }
  }
  if (y <= mid) {
    if (root->l == NULL) {
      root->l = new hor(y);
    }
    modify(root->l, l, mid, y, g);
  } else {
    if (root->r == NULL) {
      root->r = new hor(y);
    }
    modify(root->r, mid + 1, r, y, g);
  }
  root->g = gcd(root->l == NULL ? 0 : root->l->g, root->r == NULL ? 0 : root->r->g);
}

void modify(ver* root, int l, int r, int x, int y, long long g) {
  if (root->h == NULL) {
    root->h = new hor(y);
  }
  if (l == r) {
    modify(root->h, 0, m - 1, y, g);
  } else {
    if (root->l == NULL) {
      root->l = new ver();
    }
    if (root->r == NULL) {
      root->r = new ver();
    }
    int mid = (l + r) >> 1;
    if (x <= mid) {
      modify(root->l, l, mid, x, y, g);
    } else {
      modify(root->r, mid + 1, r, x, y, g);
    }
    modify(root->h, 0, m - 1, y, gcd(query(root->l->h, 0, m - 1, y, y), query(root->r->h, 0, m - 1, y, y)));
  }
}

void init(int R, int C) {
  n = R;
  m = C;
  root = new ver();
}

void update(int P, int Q, long long K) {
  modify(root, 0, n - 1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
  return query(root, 0, n - 1, 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 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 569 ms 10360 KB Output is correct
5 Correct 376 ms 10488 KB Output is correct
6 Correct 604 ms 7432 KB Output is correct
7 Correct 712 ms 7156 KB Output is correct
8 Correct 485 ms 5520 KB Output is correct
9 Correct 789 ms 7260 KB Output is correct
10 Correct 721 ms 6836 KB Output is correct
11 Correct 2 ms 512 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 356 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1117 ms 13744 KB Output is correct
13 Correct 1782 ms 7096 KB Output is correct
14 Correct 341 ms 1972 KB Output is correct
15 Correct 2276 ms 8596 KB Output is correct
16 Correct 292 ms 12228 KB Output is correct
17 Correct 1089 ms 8020 KB Output is correct
18 Correct 2461 ms 12664 KB Output is correct
19 Correct 1942 ms 12812 KB Output is correct
20 Correct 2021 ms 12184 KB Output is correct
21 Correct 2 ms 512 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 572 ms 10228 KB Output is correct
13 Correct 573 ms 10552 KB Output is correct
14 Correct 685 ms 7492 KB Output is correct
15 Correct 728 ms 7288 KB Output is correct
16 Correct 338 ms 5624 KB Output is correct
17 Correct 634 ms 7304 KB Output is correct
18 Correct 537 ms 6940 KB Output is correct
19 Correct 1046 ms 13708 KB Output is correct
20 Correct 1762 ms 7032 KB Output is correct
21 Correct 301 ms 1912 KB Output is correct
22 Correct 2151 ms 8512 KB Output is correct
23 Correct 266 ms 12224 KB Output is correct
24 Correct 964 ms 7924 KB Output is correct
25 Correct 2124 ms 12664 KB Output is correct
26 Correct 1809 ms 12688 KB Output is correct
27 Correct 1633 ms 12380 KB Output is correct
28 Correct 775 ms 43768 KB Output is correct
29 Correct 1727 ms 39364 KB Output is correct
30 Correct 5260 ms 40224 KB Output is correct
31 Correct 4635 ms 30948 KB Output is correct
32 Correct 657 ms 2376 KB Output is correct
33 Correct 902 ms 5824 KB Output is correct
34 Correct 356 ms 36204 KB Output is correct
35 Correct 1609 ms 19560 KB Output is correct
36 Correct 3369 ms 36592 KB Output is correct
37 Correct 2739 ms 36732 KB Output is correct
38 Correct 2563 ms 36200 KB Output is correct
39 Correct 2061 ms 28604 KB Output is correct
40 Correct 2 ms 256 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 432 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 652 ms 10304 KB Output is correct
13 Correct 439 ms 10600 KB Output is correct
14 Correct 617 ms 7428 KB Output is correct
15 Correct 840 ms 7308 KB Output is correct
16 Correct 365 ms 5452 KB Output is correct
17 Correct 808 ms 7288 KB Output is correct
18 Correct 800 ms 6776 KB Output is correct
19 Correct 1071 ms 13688 KB Output is correct
20 Correct 1775 ms 7124 KB Output is correct
21 Correct 301 ms 1912 KB Output is correct
22 Correct 2249 ms 8440 KB Output is correct
23 Correct 281 ms 12280 KB Output is correct
24 Correct 1260 ms 8104 KB Output is correct
25 Correct 2346 ms 12664 KB Output is correct
26 Correct 1930 ms 12660 KB Output is correct
27 Correct 1611 ms 12224 KB Output is correct
28 Correct 799 ms 43564 KB Output is correct
29 Correct 1715 ms 39140 KB Output is correct
30 Correct 5228 ms 40212 KB Output is correct
31 Correct 4495 ms 30868 KB Output is correct
32 Correct 578 ms 2376 KB Output is correct
33 Correct 850 ms 6136 KB Output is correct
34 Correct 364 ms 36300 KB Output is correct
35 Correct 1628 ms 19576 KB Output is correct
36 Correct 3021 ms 36600 KB Output is correct
37 Correct 2543 ms 36828 KB Output is correct
38 Correct 2316 ms 36296 KB Output is correct
39 Correct 1302 ms 95480 KB Output is correct
40 Correct 3145 ms 79044 KB Output is correct
41 Correct 7093 ms 85452 KB Output is correct
42 Correct 6326 ms 70812 KB Output is correct
43 Correct 732 ms 83960 KB Output is correct
44 Correct 775 ms 11192 KB Output is correct
45 Correct 2223 ms 38136 KB Output is correct
46 Correct 4428 ms 88092 KB Output is correct
47 Correct 4204 ms 88056 KB Output is correct
48 Correct 4057 ms 87704 KB Output is correct
49 Correct 2 ms 384 KB Output is correct