oj.uz

Submission #437278

# Submission time Handle Problem Language Result Execution time Memory
437278 2021-06-26T06:36:33 Z Mackerel_Pike Game (IOI13_game) C++14
80 / 100
 4769 ms 256004 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 = 2e7 + 5;
  static const int siz = 1000000000;
  int tot, r;
  int ls[maxv], rs[maxv], rt[maxv];
  ll dat[maxv];
  inline void init(){ r = 0, tot = 1; return; }
  inline void update2(int q, ll k, int &u, int l = 0, int r = siz - 1){
    if(!u)
      u = tot++, 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, ls[u], l, md);
    else
      update2(q, k, rs[u], md + 1, r);
    dat[u] = gcd2(dat[ls[u]], dat[rs[u]]);
    return;
  }

  inline void pushUp(int q, int &v, int vl, int vr, int l = 0, int r = siz - 1){
    if(!v)
      v = tot++, dat[v] = 0;
    if(l == r){
      dat[v] = gcd2(dat[vl], dat[vr]);
      return;
    }
    int md = l + r >> 1;
    if(q <= md)
      pushUp(q, ls[v], ls[vl], ls[vr], l, md);
    else
      pushUp(q, rs[v], rs[vl], rs[vr], md + 1, r);
    dat[v] = gcd2(dat[ls[v]], dat[rs[v]]);
    return;
  }
  
  inline void update(int p, int q, ll k, int &u, int l = 0, int r = siz - 1){
    if(!u)
      u = tot++, dat[u] = 0;
    //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, rs[u], md + 1, r);
    if(t <= md)
      return query2(s, t, ls[u], l, md);
    return gcd2(query2(s, t, ls[u], l, md), query2(s, t, rs[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:32:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |     int md = l + r >> 1;
      |              ~~^~~
game.cpp: In member function 'void SegmentTree::pushUp(int, int&, int, int, int, int)':
game.cpp:48:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |     int md = l + r >> 1;
      |              ~~^~~
game.cpp: In member function 'void SegmentTree::update(int, int, ll, int&, int, int)':
game.cpp:65:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |     int md = l + r >> 1;
      |              ~~^~~
game.cpp: In member function 'll SegmentTree::query2(int, int, int, int, int)':
game.cpp:82:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |     int md = l + r >> 1;
      |              ~~^~~
game.cpp: In member function 'll SegmentTree::query(int, int, int, int, int, int, int)':
game.cpp:95:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   95 |     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 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 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 712 ms 27356 KB Output is correct
5 Correct 519 ms 27556 KB Output is correct
6 Correct 740 ms 24644 KB Output is correct
7 Correct 773 ms 24192 KB Output is correct
8 Correct 463 ms 15300 KB Output is correct
9 Correct 781 ms 24456 KB Output is correct
10 Correct 770 ms 23912 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 204 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 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1092 ms 12568 KB Output is correct
13 Correct 1419 ms 5896 KB Output is correct
14 Correct 403 ms 936 KB Output is correct
15 Correct 1568 ms 8916 KB Output is correct
16 Correct 458 ms 14388 KB Output is correct
17 Correct 962 ms 10796 KB Output is correct
18 Correct 1809 ms 14792 KB Output is correct
19 Correct 1571 ms 15036 KB Output is correct
20 Correct 1428 ms 14372 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 204 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 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 732 ms 27452 KB Output is correct
13 Correct 518 ms 27532 KB Output is correct
14 Correct 718 ms 24592 KB Output is correct
15 Correct 797 ms 24260 KB Output is correct
16 Correct 456 ms 15296 KB Output is correct
17 Correct 809 ms 24604 KB Output is correct
18 Correct 741 ms 24032 KB Output is correct
19 Correct 981 ms 12764 KB Output is correct
20 Correct 1360 ms 5868 KB Output is correct
21 Correct 425 ms 1148 KB Output is correct
22 Correct 1570 ms 8824 KB Output is correct
23 Correct 421 ms 14476 KB Output is correct
24 Correct 1024 ms 10760 KB Output is correct
25 Correct 1749 ms 14804 KB Output is correct
26 Correct 1501 ms 14968 KB Output is correct
27 Correct 1378 ms 14280 KB Output is correct
28 Correct 842 ms 157556 KB Output is correct
29 Correct 2055 ms 175624 KB Output is correct
30 Correct 4769 ms 119824 KB Output is correct
31 Correct 4404 ms 91460 KB Output is correct
32 Correct 439 ms 1048 KB Output is correct
33 Correct 592 ms 2628 KB Output is correct
34 Correct 472 ms 172900 KB Output is correct
35 Correct 1531 ms 87992 KB Output is correct
36 Correct 3098 ms 173112 KB Output is correct
37 Correct 2444 ms 173428 KB Output is correct
38 Correct 2509 ms 172848 KB Output is correct
39 Correct 2016 ms 133140 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 204 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 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 680 ms 27328 KB Output is correct
13 Correct 515 ms 27548 KB Output is correct
14 Correct 712 ms 24384 KB Output is correct
15 Correct 742 ms 24200 KB Output is correct
16 Correct 515 ms 15308 KB Output is correct
17 Correct 734 ms 24452 KB Output is correct
18 Correct 671 ms 23856 KB Output is correct
19 Correct 955 ms 12456 KB Output is correct
20 Correct 1435 ms 5884 KB Output is correct
21 Correct 434 ms 1016 KB Output is correct
22 Correct 1589 ms 8768 KB Output is correct
23 Correct 437 ms 14504 KB Output is correct
24 Correct 962 ms 10728 KB Output is correct
25 Correct 1703 ms 14680 KB Output is correct
26 Correct 1469 ms 14996 KB Output is correct
27 Correct 1460 ms 14404 KB Output is correct
28 Correct 808 ms 157784 KB Output is correct
29 Correct 2123 ms 175808 KB Output is correct
30 Correct 4760 ms 119616 KB Output is correct
31 Correct 4351 ms 91576 KB Output is correct
32 Correct 440 ms 1076 KB Output is correct
33 Correct 589 ms 2680 KB Output is correct
34 Correct 450 ms 172820 KB Output is correct
35 Correct 1518 ms 87828 KB Output is correct
36 Correct 2987 ms 173300 KB Output is correct
37 Correct 2556 ms 173216 KB Output is correct
38 Correct 2541 ms 172684 KB Output is correct
39 Runtime error 783 ms 256004 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -