oj.uz

Submission #437441

# Submission time Handle Problem Language Result Execution time Memory
437441 2021-06-26T10:19:27 Z Mackerel_Pike Game (IOI13_game) C++14
100 / 100
 7361 ms 47664 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

mt19937 rnd(2226701);

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 siz = 1000000000;

  class Trp{
  public:
    Trp *ls, *rs;
    int pos, fix;
    ll k, g;
    Trp(ll k_, ll pos_): k(k_), g(k_), pos(pos_), fix(rnd()){}
  } ;
  
  class Seg{
  public:
    Seg *ls, *rs;
    Trp *rt;
    Seg(): ls(NULL), rs(NULL), rt(NULL){}
  } *r;

  inline void init(){ r = NULL; return; }
  
  inline void pushUp(Trp *&u){
    Trp *ps = u -> ls, *qs = u -> rs;
    u -> g = u -> k;
    u -> g = gcd2(u -> g, ps == NULL ? 0 : ps -> g);
    u -> g = gcd2(u -> g, qs == NULL ? 0 : qs -> g);
    return;
  }
  
  inline void split(Trp *u, Trp *&x, Trp *&y, int q){ // <= q in x
    if(u == NULL)
      return void(x = y = NULL);
    if(u -> pos <= q)
      split(u -> rs, u -> rs, y, q), x = u;
    else
      split(u -> ls, x, u -> ls, q), y = u;
    pushUp(u);
    return;
  }

  inline void merge(Trp *&u, Trp *x, Trp *y){
    if(x == NULL || y == NULL)
      return (void)(u = (x == NULL ? y : x));
    if(x -> fix < y -> fix)
      merge(y -> ls, x, y -> ls), u = y;
    else
      merge(x -> rs, x -> rs, y), u = x;
    pushUp(u);
    return;
  }
  
  inline void update2(Trp *&u, int q, long long k){
    Trp *x, *y, *z;
    split(u, x, z, q - 1);
    split(z, y, z, q);
    delete(y);
    y = new Trp(k, q);
    merge(u, x, y);
    merge(u, u, z);
    return;
  }

  inline ll query2(Trp *&u, int s, int t){
    Trp *x, *y, *z;
    split(u, x, y, s - 1);
    split(y, y, z, t);
    ll ret = y == NULL ? 0 : y -> g;
    merge(u, x, y);
    merge(u, u, z);
    return ret;
  }
  
  inline void update(int p, int q, ll k, Seg *&u, int l = 0, int r = siz - 1){
    if(u == NULL)
      u = new Seg();
    if(l == r){
      update2(u -> rt, q, k);
      return;
    }
    int md = l + r >> 1;
    Seg *&ps = u -> ls, *&qs = u -> rs;
    if(p <= md)
      update(p, q, k, ps, l, md);
    else
      update(p, q, k, qs, md + 1, r);
    update2(u -> rt, q, gcd2(ps == NULL ? 0 : query2(ps -> rt, q, q), qs == NULL ? 0 : query2(qs -> rt, q, q)));
    return;
  }

  inline ll query(int p, int q, int s, int t, Seg *&u, int l = 0, int r = siz - 1){
    if(u == NULL)
      return 0;
    if(l >= p && r <= q)
      return query2(u -> rt, s, t);
    int md = l + r >> 1;
    if(p > md)
      return query(p, q, s, t, u -> rs, md + 1, r);
    else if(q <= md)
      return query(p, q, s, t, u -> ls, l, md);
    return gcd2(query(p, q, s, t, u -> ls, l, md), query(p, q, s, t, u -> rs, md + 1, r));
  }
} 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 constructor 'SegmentTree::Trp::Trp(ll, ll)':
game.cpp:28:11: warning: 'SegmentTree::Trp::g' will be initialized after [-Wreorder]
   28 |     ll k, g;
      |           ^
game.cpp:27:9: warning:   'int SegmentTree::Trp::pos' [-Wreorder]
   27 |     int pos, fix;
      |         ^~~
game.cpp:29:5: warning:   when initialized here [-Wreorder]
   29 |     Trp(ll k_, ll pos_): k(k_), g(k_), pos(pos_), fix(rnd()){}
      |     ^~~
game.cpp: In member function 'void SegmentTree::update(int, int, ll, SegmentTree::Seg*&, int, int)':
game.cpp:99:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |     int md = l + r >> 1;
      |              ~~^~~
game.cpp: In member function 'll SegmentTree::query(int, int, int, int, SegmentTree::Seg*&, int, int)':
game.cpp:114:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |     int md = l + r >> 1;
      |              ~~^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1874 ms 20428 KB Output is correct
5 Correct 1196 ms 20736 KB Output is correct
6 Correct 3023 ms 17512 KB Output is correct
7 Correct 3266 ms 17324 KB Output is correct
8 Correct 1734 ms 10968 KB Output is correct
9 Correct 3081 ms 17316 KB Output is correct
10 Correct 2849 ms 17064 KB Output is correct
11 Correct 1 ms 204 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 6 ms 332 KB Output is correct
3 Correct 6 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 6 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 5 ms 400 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 1831 ms 11268 KB Output is correct
13 Correct 3386 ms 6516 KB Output is correct
14 Correct 751 ms 3160 KB Output is correct
15 Correct 3667 ms 7616 KB Output is correct
16 Correct 1454 ms 9780 KB Output is correct
17 Correct 2734 ms 7952 KB Output is correct
18 Correct 4916 ms 9996 KB Output is correct
19 Correct 4283 ms 10116 KB Output is correct
20 Correct 4000 ms 9560 KB Output is correct
21 Correct 1 ms 204 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 7 ms 332 KB Output is correct
3 Correct 6 ms 296 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 6 ms 292 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 6 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 3 ms 332 KB Output is correct
12 Correct 1797 ms 20548 KB Output is correct
13 Correct 1214 ms 20832 KB Output is correct
14 Correct 3015 ms 17492 KB Output is correct
15 Correct 3176 ms 17516 KB Output is correct
16 Correct 1808 ms 10968 KB Output is correct
17 Correct 3141 ms 17376 KB Output is correct
18 Correct 2825 ms 17060 KB Output is correct
19 Correct 1899 ms 11348 KB Output is correct
20 Correct 3522 ms 6476 KB Output is correct
21 Correct 779 ms 3116 KB Output is correct
22 Correct 3585 ms 7552 KB Output is correct
23 Correct 1399 ms 9748 KB Output is correct
24 Correct 2734 ms 7924 KB Output is correct
25 Correct 5148 ms 10004 KB Output is correct
26 Correct 4274 ms 10128 KB Output is correct
27 Correct 4009 ms 9504 KB Output is correct
28 Correct 1283 ms 22648 KB Output is correct
29 Correct 2548 ms 25736 KB Output is correct
30 Correct 4669 ms 19176 KB Output is correct
31 Correct 4041 ms 15388 KB Output is correct
32 Correct 707 ms 2816 KB Output is correct
33 Correct 1008 ms 3108 KB Output is correct
34 Correct 883 ms 23372 KB Output is correct
35 Correct 2729 ms 13352 KB Output is correct
36 Correct 5472 ms 23084 KB Output is correct
37 Correct 4187 ms 23204 KB Output is correct
38 Correct 4330 ms 22620 KB Output is correct
39 Correct 3551 ms 18740 KB Output is correct
40 Correct 1 ms 204 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 7 ms 332 KB Output is correct
3 Correct 7 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 6 ms 332 KB Output is correct
7 Correct 1 ms 292 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 5 ms 392 KB Output is correct
10 Correct 3 ms 332 KB Output is correct
11 Correct 3 ms 332 KB Output is correct
12 Correct 1800 ms 20612 KB Output is correct
13 Correct 1220 ms 20760 KB Output is correct
14 Correct 2925 ms 17772 KB Output is correct
15 Correct 3251 ms 17548 KB Output is correct
16 Correct 1705 ms 11008 KB Output is correct
17 Correct 3158 ms 17396 KB Output is correct
18 Correct 2798 ms 17032 KB Output is correct
19 Correct 1806 ms 11416 KB Output is correct
20 Correct 3453 ms 6260 KB Output is correct
21 Correct 772 ms 3184 KB Output is correct
22 Correct 3640 ms 7808 KB Output is correct
23 Correct 1374 ms 9820 KB Output is correct
24 Correct 2559 ms 8132 KB Output is correct
25 Correct 4853 ms 10220 KB Output is correct
26 Correct 4091 ms 10060 KB Output is correct
27 Correct 3721 ms 9492 KB Output is correct
28 Correct 1345 ms 22724 KB Output is correct
29 Correct 2590 ms 25740 KB Output is correct
30 Correct 4580 ms 19120 KB Output is correct
31 Correct 4070 ms 15416 KB Output is correct
32 Correct 660 ms 2840 KB Output is correct
33 Correct 998 ms 3268 KB Output is correct
34 Correct 818 ms 23488 KB Output is correct
35 Correct 2593 ms 13420 KB Output is correct
36 Correct 5315 ms 23312 KB Output is correct
37 Correct 4120 ms 23288 KB Output is correct
38 Correct 4284 ms 22660 KB Output is correct
39 Correct 1938 ms 45936 KB Output is correct
40 Correct 4484 ms 47664 KB Output is correct
41 Correct 7274 ms 37264 KB Output is correct
42 Correct 6628 ms 28828 KB Output is correct
43 Correct 1658 ms 46252 KB Output is correct
44 Correct 1190 ms 2484 KB Output is correct
45 Correct 3399 ms 18216 KB Output is correct
46 Correct 7361 ms 46072 KB Output is correct
47 Correct 6923 ms 46104 KB Output is correct
48 Correct 7264 ms 45820 KB Output is correct
49 Correct 1 ms 204 KB Output is correct