Submission #437291

#	Time	Username	Problem	Language	Result	Execution time	Memory
437291		Mackerel_Pike	Game (IOI13_game)	C++14	80 / 100	4689 ms	256000 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 SegmentTree{
public:
  static const int maxv = 5e6 + 5;
  static const int maxv2 = 1e7 + 5;
  static const int siz = 1000000000;
  int tot, tot2, r;
  int ls[maxv], rs[maxv], rt[maxv];
  int ls2[maxv2], rs2[maxv2];
  ll dat[maxv2];
  inline void init(){ r = 0, tot = tot2 = 1; return; }
  inline void update2(int q, ll k, int &u, int l = 0, int r = siz - 1){
    if(!u)
      u = tot2++, 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, ls2[u], l, md);
    else
      update2(q, k, rs2[u], md + 1, r);
    dat[u] = gcd2(dat[ls2[u]], dat[rs2[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 = tot2++, dat[v] = 0;
    if(l == r){
      dat[v] = gcd2(dat[vl], dat[vr]);
      return;
    }
    int md = l + r >> 1;
    if(q <= md)
      pushUp(q, ls2[v], ls2[vl], ls2[vr], l, md);
    else
      pushUp(q, rs2[v], rs2[vl], rs2[vr], md + 1, r);
    dat[v] = gcd2(dat[ls2[v]], dat[rs2[v]]);
    return;
  }
  
  inline void update(int p, int q, ll k, int &u, int l = 0, int r = siz - 1){
    if(!u)
      u = tot++;
    //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, rs2[u], md + 1, r);
    if(t <= md)
      return query2(s, t, ls2[u], l, md);
    return gcd2(query2(s, t, ls2[u], l, md), query2(s, t, rs2[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 (stderr)

game.cpp: In member function 'void SegmentTree::update2(int, ll, int&, int, int)':
game.cpp:34:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |     int md = l + r >> 1;
      |              ~~^~~
game.cpp: In member function 'void SegmentTree::pushUp(int, int&, int, int, int, int)':
game.cpp:52:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |     int md = l + r >> 1;
      |              ~~^~~
game.cpp: In member function 'void SegmentTree::update(int, int, ll, int&, int, int)':
game.cpp:69:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |     int md = l + r >> 1;
      |              ~~^~~
game.cpp: In member function 'll SegmentTree::query2(int, int, int, int, int)':
game.cpp:86:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |     int md = l + r >> 1;
      |              ~~^~~
game.cpp: In member function 'll SegmentTree::query(int, int, int, int, int, int, int)':
game.cpp:99:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |     int md = l + r >> 1;
      |              ~~^~~

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 0 / 20