oj.uz

Submission #437285

# Submission time Handle Problem Language Result Execution time Memory
437285 2021-06-26T06:44:12 Z Mackerel_Pike Game (IOI13_game) C++14
80 / 100
 4901 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(!vl && !vr)
      	return;
    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:50:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |     int md = l + r >> 1;
      |              ~~^~~
game.cpp: In member function 'void SegmentTree::update(int, int, ll, int&, int, int)':
game.cpp:67:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |     int md = l + r >> 1;
      |              ~~^~~
game.cpp: In member function 'll SegmentTree::query2(int, int, int, int, int)':
game.cpp:84:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |     int md = l + r >> 1;
      |              ~~^~~
game.cpp: In member function 'll SegmentTree::query(int, int, int, int, int, int, int)':
game.cpp:97:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   97 |     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 677 ms 27316 KB Output is correct
5 Correct 526 ms 27460 KB Output is correct
6 Correct 712 ms 24348 KB Output is correct
7 Correct 766 ms 24132 KB Output is correct
8 Correct 479 ms 15292 KB Output is correct
9 Correct 763 ms 24408 KB Output is correct
10 Correct 706 ms 24060 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 2 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 978 ms 12624 KB Output is correct
13 Correct 1363 ms 6088 KB Output is correct
14 Correct 400 ms 1036 KB Output is correct
15 Correct 1588 ms 8924 KB Output is correct
16 Correct 412 ms 14536 KB Output is correct
17 Correct 1028 ms 10728 KB Output is correct
18 Correct 1733 ms 14904 KB Output is correct
19 Correct 1540 ms 14800 KB Output is correct
20 Correct 1405 ms 14452 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 3 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 695 ms 27428 KB Output is correct
13 Correct 526 ms 27624 KB Output is correct
14 Correct 705 ms 24376 KB Output is correct
15 Correct 759 ms 24128 KB Output is correct
16 Correct 506 ms 15344 KB Output is correct
17 Correct 752 ms 24500 KB Output is correct
18 Correct 714 ms 23920 KB Output is correct
19 Correct 1002 ms 12488 KB Output is correct
20 Correct 1373 ms 5884 KB Output is correct
21 Correct 406 ms 984 KB Output is correct
22 Correct 1605 ms 9044 KB Output is correct
23 Correct 410 ms 14496 KB Output is correct
24 Correct 976 ms 10684 KB Output is correct
25 Correct 1743 ms 14848 KB Output is correct
26 Correct 1560 ms 15032 KB Output is correct
27 Correct 1413 ms 14492 KB Output is correct
28 Correct 807 ms 157632 KB Output is correct
29 Correct 2084 ms 175604 KB Output is correct
30 Correct 4901 ms 119592 KB Output is correct
31 Correct 4441 ms 91320 KB Output is correct
32 Correct 450 ms 1092 KB Output is correct
33 Correct 607 ms 2728 KB Output is correct
34 Correct 460 ms 172844 KB Output is correct
35 Correct 1483 ms 87824 KB Output is correct
36 Correct 3088 ms 173228 KB Output is correct
37 Correct 2388 ms 173356 KB Output is correct
38 Correct 2540 ms 172772 KB Output is correct
39 Correct 2050 ms 133380 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 753 ms 27252 KB Output is correct
13 Correct 549 ms 27476 KB Output is correct
14 Correct 789 ms 24372 KB Output is correct
15 Correct 780 ms 24184 KB Output is correct
16 Correct 473 ms 15292 KB Output is correct
17 Correct 762 ms 24444 KB Output is correct
18 Correct 715 ms 23892 KB Output is correct
19 Correct 1000 ms 12776 KB Output is correct
20 Correct 1358 ms 6188 KB Output is correct
21 Correct 403 ms 1020 KB Output is correct
22 Correct 1592 ms 8952 KB Output is correct
23 Correct 411 ms 14532 KB Output is correct
24 Correct 963 ms 10692 KB Output is correct
25 Correct 1728 ms 14976 KB Output is correct
26 Correct 1462 ms 14888 KB Output is correct
27 Correct 1394 ms 14356 KB Output is correct
28 Correct 789 ms 157556 KB Output is correct
29 Correct 2098 ms 175728 KB Output is correct
30 Correct 4752 ms 119684 KB Output is correct
31 Correct 4396 ms 91512 KB Output is correct
32 Correct 447 ms 1116 KB Output is correct
33 Correct 603 ms 2632 KB Output is correct
34 Correct 460 ms 172740 KB Output is correct
35 Correct 1520 ms 87960 KB Output is correct
36 Correct 3004 ms 173372 KB Output is correct
37 Correct 2443 ms 173408 KB Output is correct
38 Correct 2422 ms 172704 KB Output is correct
39 Runtime error 797 ms 256004 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -