oj.uz

Submission #437291

# Submission time Handle Problem Language Result Execution time Memory
437291 2021-06-26T06:49:40 Z Mackerel_Pike Game (IOI13_game) C++14
80 / 100
 4689 ms 256000 KB 
#include "game.h"
#include <bits/stdc++.h>

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;
}

class SegmentTree{
public:
  static const int maxv = 5e6 + 5;
  static const int maxv2 = 1e7 + 5;
  static const int siz = 1000000000;
  int tot, tot2, r;
  int ls[maxv], rs[maxv], rt[maxv];
  int ls2[maxv2], rs2[maxv2];
  ll dat[maxv2];
  inline void init(){ r = 0, tot = tot2 = 1; return; }
  inline void update2(int q, ll k, int &u, int l = 0, int r = siz - 1){
    if(!u)
      u = tot2++, dat[u] = 0;
    //printf("update2 u = %d l = %d r = %d\n", u, l, r);
    if(l == r){
      dat[u] = k;
      return;
    }
    int md = l + r >> 1;
    if(q <= md)
      update2(q, k, ls2[u], l, md);
    else
      update2(q, k, rs2[u], md + 1, r);
    dat[u] = gcd2(dat[ls2[u]], dat[rs2[u]]);
    return;
  }

  inline void pushUp(int q, int &v, int vl, int vr, int l = 0, int r = siz - 1){
    if(!vl && !vr)
      return;
    if(!v)
      v = tot2++, dat[v] = 0;
    if(l == r){
      dat[v] = gcd2(dat[vl], dat[vr]);
      return;
    }
    int md = l + r >> 1;
    if(q <= md)
      pushUp(q, ls2[v], ls2[vl], ls2[vr], l, md);
    else
      pushUp(q, rs2[v], rs2[vl], rs2[vr], md + 1, r);
    dat[v] = gcd2(dat[ls2[v]], dat[rs2[v]]);
    return;
  }
  
  inline void update(int p, int q, ll k, int &u, int l = 0, int r = siz - 1){
    if(!u)
      u = tot++;
    //printf("update u = %d rt = %d\n", u, rt[u]);
    if(l == r){
      update2(q, k, rt[u]);
      return;
    }
    int md = l + r >> 1;
    if(p <= md)
      update(p, q, k, ls[u], l, md);
    else
      update(p, q, k, rs[u], md + 1, r);
    pushUp(q, rt[u], rt[ls[u]], rt[rs[u]]);
    return;
  }

  inline ll query2(int s, int t, int u, int l = 0, int r = siz - 1){
    //printf("query2 u = %d\n", u);
    if(!u){
      return 0;
    }
    if(l >= s && r <= t){
      return dat[u];
    }
    int md = l + r >> 1;
    if(s > md)
      return query2(s, t, rs2[u], md + 1, r);
    if(t <= md)
      return query2(s, t, ls2[u], l, md);
    return gcd2(query2(s, t, ls2[u], l, md), query2(s, t, rs2[u], md + 1, r));
  }

  inline ll query(int p, int q, int s, int t, int u, int l = 0, int r = siz - 1){
    if(!u)
      return 0;
    if(l >= p && r <= q)
      return query2(s, t, rt[u]);
    int md = l + r >> 1;
    if(p > md)
      return query(p, q, s, t, rs[u], md + 1, r);
    if(q <= md)
      return query(p, q, s, t, ls[u], l, md);
    return gcd2(query(p, q, s, t, rs[u], md + 1, r), query(p, q, s, t, ls[u], l, md));
  }
} seg;

void init(int R, int C) {
  seg.init();
}

void update(int P, int Q, long long K) {
  seg.update(P, Q, K, seg.r);
  return;
}

long long calculate(int P, int Q, int U, int V) {
  return seg.query(P, U, Q, V, seg.r);
}

Compilation message

game.cpp: In member function 'void SegmentTree::update2(int, ll, int&, int, int)':
game.cpp:34:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |     int md = l + r >> 1;
      |              ~~^~~
game.cpp: In member function 'void SegmentTree::pushUp(int, int&, int, int, int, int)':
game.cpp:52:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |     int md = l + r >> 1;
      |              ~~^~~
game.cpp: In member function 'void SegmentTree::update(int, int, ll, int&, int, int)':
game.cpp:69:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |     int md = l + r >> 1;
      |              ~~^~~
game.cpp: In member function 'll SegmentTree::query2(int, int, int, int, int)':
game.cpp:86:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |     int md = l + r >> 1;
      |              ~~^~~
game.cpp: In member function 'll SegmentTree::query(int, int, int, int, int, int, int)':
game.cpp:99:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |     int md = l + r >> 1;
      |              ~~^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 662 ms 27320 KB Output is correct
5 Correct 559 ms 27564 KB Output is correct
6 Correct 708 ms 24544 KB Output is correct
7 Correct 809 ms 24216 KB Output is correct
8 Correct 469 ms 15412 KB Output is correct
9 Correct 854 ms 24372 KB Output is correct
10 Correct 842 ms 23832 KB Output is correct
11 Correct 1 ms 332 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 949 ms 11488 KB Output is correct
13 Correct 1366 ms 5036 KB Output is correct
14 Correct 419 ms 1004 KB Output is correct
15 Correct 1593 ms 7232 KB Output is correct
16 Correct 408 ms 12228 KB Output is correct
17 Correct 1002 ms 8920 KB Output is correct
18 Correct 1827 ms 12492 KB Output is correct
19 Correct 1476 ms 12668 KB Output is correct
20 Correct 1415 ms 12048 KB Output is correct
21 Correct 1 ms 332 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 656 ms 27332 KB Output is correct
13 Correct 557 ms 27492 KB Output is correct
14 Correct 718 ms 24388 KB Output is correct
15 Correct 753 ms 24180 KB Output is correct
16 Correct 574 ms 15424 KB Output is correct
17 Correct 735 ms 24396 KB Output is correct
18 Correct 775 ms 23932 KB Output is correct
19 Correct 932 ms 11480 KB Output is correct
20 Correct 1413 ms 5052 KB Output is correct
21 Correct 404 ms 960 KB Output is correct
22 Correct 1538 ms 7212 KB Output is correct
23 Correct 427 ms 12232 KB Output is correct
24 Correct 909 ms 8900 KB Output is correct
25 Correct 1815 ms 12504 KB Output is correct
26 Correct 1372 ms 12564 KB Output is correct
27 Correct 1349 ms 12156 KB Output is correct
28 Correct 743 ms 125636 KB Output is correct
29 Correct 2015 ms 140720 KB Output is correct
30 Correct 4603 ms 101764 KB Output is correct
31 Correct 4396 ms 77900 KB Output is correct
32 Correct 443 ms 1060 KB Output is correct
33 Correct 653 ms 2344 KB Output is correct
34 Correct 472 ms 137792 KB Output is correct
35 Correct 1573 ms 70300 KB Output is correct
36 Correct 3052 ms 138048 KB Output is correct
37 Correct 2615 ms 138212 KB Output is correct
38 Correct 2392 ms 137736 KB Output is correct
39 Correct 2095 ms 106260 KB Output is correct
40 Correct 1 ms 332 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 735 ms 27300 KB Output is correct
13 Correct 529 ms 27472 KB Output is correct
14 Correct 754 ms 24372 KB Output is correct
15 Correct 760 ms 24148 KB Output is correct
16 Correct 475 ms 15356 KB Output is correct
17 Correct 843 ms 24488 KB Output is correct
18 Correct 776 ms 23956 KB Output is correct
19 Correct 919 ms 11556 KB Output is correct
20 Correct 1306 ms 4940 KB Output is correct
21 Correct 404 ms 1112 KB Output is correct
22 Correct 1725 ms 7236 KB Output is correct
23 Correct 419 ms 12200 KB Output is correct
24 Correct 946 ms 9080 KB Output is correct
25 Correct 1943 ms 12448 KB Output is correct
26 Correct 1440 ms 12640 KB Output is correct
27 Correct 1527 ms 12052 KB Output is correct
28 Correct 834 ms 125496 KB Output is correct
29 Correct 2024 ms 140668 KB Output is correct
30 Correct 4689 ms 101708 KB Output is correct
31 Correct 4290 ms 77836 KB Output is correct
32 Correct 457 ms 964 KB Output is correct
33 Correct 608 ms 2456 KB Output is correct
34 Correct 443 ms 137700 KB Output is correct
35 Correct 1525 ms 70276 KB Output is correct
36 Correct 2902 ms 138116 KB Output is correct
37 Correct 2406 ms 138236 KB Output is correct
38 Correct 2333 ms 137636 KB Output is correct
39 Runtime error 701 ms 256000 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -