oj.uz

답안 #437275

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
437275 2021-06-26T06:32:48 Z Mackerel_Pike 게임 (IOI13_game) C++14
80 / 100
 4953 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 = 1e7 + 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 552 KB Output is correct
3 Correct 2 ms 556 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 300 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 1 ms 332 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 759 ms 31656 KB Output is correct
5 Correct 604 ms 31520 KB Output is correct
6 Correct 868 ms 29180 KB Output is correct
7 Correct 963 ms 28808 KB Output is correct
8 Correct 475 ms 19536 KB Output is correct
9 Correct 801 ms 29044 KB Output is correct
10 Correct 802 ms 28512 KB Output is correct
11 Correct 1 ms 332 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 3 ms 552 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 296 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 970 ms 16644 KB Output is correct
13 Correct 1385 ms 9776 KB Output is correct
14 Correct 419 ms 5828 KB Output is correct
15 Correct 1653 ms 13236 KB Output is correct
16 Correct 462 ms 18692 KB Output is correct
17 Correct 934 ms 15592 KB Output is correct
18 Correct 1706 ms 20068 KB Output is correct
19 Correct 1428 ms 20164 KB Output is correct
20 Correct 1403 ms 19780 KB Output is correct
21 Correct 1 ms 332 KB Output is correct

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 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 767 ms 31716 KB Output is correct
13 Correct 514 ms 31492 KB Output is correct
14 Correct 725 ms 29056 KB Output is correct
15 Correct 759 ms 28840 KB Output is correct
16 Correct 455 ms 19560 KB Output is correct
17 Correct 806 ms 28976 KB Output is correct
18 Correct 722 ms 28500 KB Output is correct
19 Correct 1000 ms 16580 KB Output is correct
20 Correct 1342 ms 9872 KB Output is correct
21 Correct 415 ms 5680 KB Output is correct
22 Correct 1580 ms 13204 KB Output is correct
23 Correct 505 ms 18708 KB Output is correct
24 Correct 939 ms 15568 KB Output is correct
25 Correct 1694 ms 20068 KB Output is correct
26 Correct 1378 ms 20240 KB Output is correct
27 Correct 1410 ms 19740 KB Output is correct
28 Correct 857 ms 168048 KB Output is correct
29 Correct 2182 ms 185816 KB Output is correct
30 Correct 4718 ms 126540 KB Output is correct
31 Correct 4433 ms 98264 KB Output is correct
32 Correct 443 ms 10280 KB Output is correct
33 Correct 633 ms 11896 KB Output is correct
34 Correct 492 ms 179616 KB Output is correct
35 Correct 1547 ms 97732 KB Output is correct
36 Correct 3387 ms 183852 KB Output is correct
37 Correct 2430 ms 183812 KB Output is correct
38 Correct 2676 ms 183328 KB Output is correct
39 Correct 2015 ms 143332 KB Output is correct
40 Correct 1 ms 332 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 4 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 304 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 758 ms 31656 KB Output is correct
13 Correct 530 ms 31468 KB Output is correct
14 Correct 866 ms 29044 KB Output is correct
15 Correct 872 ms 28768 KB Output is correct
16 Correct 518 ms 19604 KB Output is correct
17 Correct 751 ms 28960 KB Output is correct
18 Correct 775 ms 28556 KB Output is correct
19 Correct 1049 ms 16732 KB Output is correct
20 Correct 1376 ms 9896 KB Output is correct
21 Correct 405 ms 5752 KB Output is correct
22 Correct 1574 ms 13144 KB Output is correct
23 Correct 420 ms 18628 KB Output is correct
24 Correct 1025 ms 15552 KB Output is correct
25 Correct 1644 ms 20084 KB Output is correct
26 Correct 1417 ms 20128 KB Output is correct
27 Correct 1436 ms 19560 KB Output is correct
28 Correct 839 ms 168044 KB Output is correct
29 Correct 2199 ms 185884 KB Output is correct
30 Correct 4953 ms 126628 KB Output is correct
31 Correct 4526 ms 98284 KB Output is correct
32 Correct 453 ms 10328 KB Output is correct
33 Correct 663 ms 11860 KB Output is correct
34 Correct 536 ms 179524 KB Output is correct
35 Correct 1530 ms 97796 KB Output is correct
36 Correct 3356 ms 183788 KB Output is correct
37 Correct 2522 ms 183804 KB Output is correct
38 Correct 2623 ms 183352 KB Output is correct
39 Runtime error 842 ms 256000 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -