제출 #437316

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
437316		Mackerel_Pike	게임 (IOI13_game)	C++14	63 / 100	2035 ms	256004 KiB

game

#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);
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20