oj.uz

Submission #437316

# Submission time Handle Problem Language Result Execution time Memory
437316 2021-06-26T07:09:48 Z Mackerel_Pike Game (IOI13_game) C++14
63 / 100
 2035 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 SHIT{
public:
  SHIT *ls, *rs;
  ll dat;
  SHIT(): ls(NULL), rs(NULL){}
} ;

class FUCK{
public:
  FUCK *ls, *rs;
  SHIT *rt;
  FUCK(): ls(NULL), rs(NULL), rt(NULL){}
} ;

class SegmentTree{
public:
  static const int maxv = 5e6 + 5;
  static const int maxv2 = 1e7 + 5;
  static const int siz = 1000000000;
  FUCK *r;
  inline void init(){ r = NULL; return; }
  inline void update2(int q, ll k, SHIT *&u, int l = 0, int r = siz - 1){
    if(u == NULL)
      u = new SHIT();
    //printf("update2 u = %d l = %d r = %d\n", u, l, r);
    if(l == r){
      u -> dat = k;
      return;
    }
    int md = l + r >> 1;
    SHIT *&ps = u -> ls, *&qs = u -> rs;
    if(q <= md)
      update2(q, k, ps, l, md);
    else
      update2(q, k, qs, md + 1, r);
    u -> dat = gcd2(ps == NULL ? 0 : ps -> dat, qs == NULL ? 0 : qs -> dat);
    return;
  }

  inline void pushUp(int q, SHIT *&v, SHIT *vl, SHIT *vr, int l = 0, int r = siz - 1){
    if(vl == NULL && vr == NULL)
      return;
    if(v == NULL)
      v = new SHIT();
    if(l == r){
      v -> dat = gcd2(vl != NULL ? vl -> dat : 0, vr != NULL ? vr -> dat : 0);
      return;
    }
    int md = l + r >> 1;
    SHIT *&ps = v -> ls, *&qs = v -> rs;
    if(q <= md)
      pushUp(q, ps, vl == NULL ? NULL : vl -> ls, vr == NULL ? NULL : vr -> ls, l, md);
    else
      pushUp(q, qs, vl == NULL ? NULL : vl -> rs, vr == NULL ? NULL : vr -> rs, md + 1, r);
    v -> dat = gcd2(ps == NULL ? 0 : ps -> dat, qs == NULL ? 0 : qs -> dat);
    return;
  }
  
  inline void update(int p, int q, ll k, FUCK *&u, int l = 0, int r = siz - 1){
    if(u == NULL)
      u = new FUCK();
    //printf("update u = %d rt = %d\n", u, rt[u]);
    if(l == r){
      update2(q, k, u -> rt);
      return;
    }
    int md = l + r >> 1;
    FUCK *&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);
    pushUp(q, u -> rt, ps == NULL ? NULL : ps -> rt, qs == NULL ? NULL : qs -> rt);
    return;
  }

  inline ll query2(int s, int t, SHIT *&u, int l = 0, int r = siz - 1){
    //printf("query2 u = %d\n", u);
    if(u == NULL){
      return 0;
    }
    if(l >= s && r <= t){
      return u -> dat;
    }
    int md = l + r >> 1;
    if(s > md)
      return query2(s, t, u -> rs, md + 1, r);
    if(t <= md)
      return query2(s, t, u -> ls, l, md);
    return gcd2(query2(s, t, u -> ls, l, md), query2(s, t, u -> rs, md + 1, r));
  }

  inline ll query(int p, int q, int s, int t, FUCK *&u, int l = 0, int r = siz - 1){
    if(u == NULL)
      return 0;
    if(l >= p && r <= q)
      return query2(s, t, u -> rt);
    int md = l + r >> 1;
    if(p > md)
      return query(p, q, s, t, u -> rs, md + 1, r);
    if(q <= md)
      return query(p, q, s, t, u -> ls, l, md);
    return gcd2(query(p, q, s, t, u -> rs, md + 1, r), query(p, q, s, t, u -> ls, 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, SHIT*&, int, int)':
game.cpp:45:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |     int md = l + r >> 1;
      |              ~~^~~
game.cpp: In member function 'void SegmentTree::pushUp(int, SHIT*&, SHIT*, SHIT*, int, int)':
game.cpp:64:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |     int md = l + r >> 1;
      |              ~~^~~
game.cpp: In member function 'void SegmentTree::update(int, int, ll, FUCK*&, 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::query2(int, int, SHIT*&, int, int)':
game.cpp:100:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |     int md = l + r >> 1;
      |              ~~^~~
game.cpp: In member function 'll SegmentTree::query(int, int, int, int, FUCK*&, int, int)':
game.cpp:113:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  113 |     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 3 ms 588 KB Output is correct
3 Correct 3 ms 588 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 3 ms 548 KB Output is correct
7 Correct 1 ms 288 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 3 ms 588 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 2 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 2 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 717 ms 50304 KB Output is correct
5 Correct 591 ms 50376 KB Output is correct
6 Correct 792 ms 47504 KB Output is correct
7 Correct 872 ms 47412 KB Output is correct
8 Correct 498 ms 28876 KB Output is correct
9 Correct 816 ms 47636 KB Output is correct
10 Correct 747 ms 46960 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 3 ms 588 KB Output is correct
3 Correct 3 ms 588 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 3 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 588 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 895 ms 18672 KB Output is correct
13 Correct 1386 ms 8892 KB Output is correct
14 Correct 393 ms 1148 KB Output is correct
15 Correct 1503 ms 13732 KB Output is correct
16 Correct 452 ms 23328 KB Output is correct
17 Correct 1071 ms 16208 KB Output is correct
18 Correct 2035 ms 23616 KB Output is correct
19 Correct 1854 ms 23736 KB Output is correct
20 Correct 1616 ms 23148 KB Output is correct
21 Correct 1 ms 204 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 3 ms 588 KB Output is correct
3 Correct 3 ms 588 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 3 ms 552 KB Output is correct
7 Correct 1 ms 288 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 588 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 789 ms 50304 KB Output is correct
13 Correct 611 ms 50432 KB Output is correct
14 Correct 829 ms 47480 KB Output is correct
15 Correct 825 ms 47172 KB Output is correct
16 Correct 524 ms 28776 KB Output is correct
17 Correct 852 ms 47472 KB Output is correct
18 Correct 802 ms 46960 KB Output is correct
19 Correct 966 ms 18728 KB Output is correct
20 Correct 1285 ms 8880 KB Output is correct
21 Correct 409 ms 1180 KB Output is correct
22 Correct 1520 ms 13516 KB Output is correct
23 Correct 459 ms 23404 KB Output is correct
24 Correct 1102 ms 16288 KB Output is correct
25 Correct 1789 ms 23628 KB Output is correct
26 Correct 1633 ms 23924 KB Output is correct
27 Correct 1532 ms 23208 KB Output is correct
28 Correct 1020 ms 251932 KB Output is correct
29 Runtime error 1808 ms 256004 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 3 ms 588 KB Output is correct
3 Correct 3 ms 588 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 588 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 720 ms 50396 KB Output is correct
13 Correct 585 ms 50372 KB Output is correct
14 Correct 805 ms 47436 KB Output is correct
15 Correct 880 ms 47300 KB Output is correct
16 Correct 554 ms 28740 KB Output is correct
17 Correct 819 ms 47504 KB Output is correct
18 Correct 802 ms 46916 KB Output is correct
19 Correct 906 ms 18544 KB Output is correct
20 Correct 1283 ms 8920 KB Output is correct
21 Correct 402 ms 1264 KB Output is correct
22 Correct 1474 ms 13556 KB Output is correct
23 Correct 448 ms 23388 KB Output is correct
24 Correct 1086 ms 16148 KB Output is correct
25 Correct 1914 ms 23860 KB Output is correct
26 Correct 1693 ms 23916 KB Output is correct
27 Correct 1516 ms 23392 KB Output is correct
28 Correct 1014 ms 251684 KB Output is correct
29 Runtime error 1763 ms 256004 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -