Submission #437441

#	Time	Username	Problem	Language	Result	Execution time	Memory
437441		Mackerel_Pike	Game (IOI13_game)	C++14	100 / 100	7361 ms	47664 KiB

game

#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 (stderr)

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