Submission #507643

#	Time	Username	Problem	Language	Result	Execution time	Memory
507643		sofapuden	Game (IOI13_game)	C++14	63 / 100	1805 ms	256004 KiB

game

#include "game.h"
#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

ll gcd2(ll X, ll Y) {
  ll tmp;
  while (X != Y && Y != 0) {
    tmp = X;
    X = Y;
    Y = tmp % Y;
  }
  return X;
}

long long mxN = 1<<30;

struct seg1d{

  int lb, rb;
  ll val;

  seg1d *l, *r;

  seg1d () : l(NULL), r(NULL), val(0) {}

  inline void init(int lx, int rx){
    lb = lx, rb = rx;
  }

  inline void exl(){
    int mid = (lb+rb)>>1;
    l = new seg1d;
    l->init(lb,mid);
  }
  inline void exr(){
    int mid = (lb+rb)>>1;
    r = new seg1d;
    r->init(mid+1,rb);
  }

  ll getGCD(int llb, int rrb){
    if(llb > rb || rrb < lb)return 0;
    if(llb <= lb && rrb >= rb)return val;
    if(l == NULL && r == NULL)return 0;
    if(l == NULL)return r->getGCD(llb,rrb);
    if(r == NULL)return l->getGCD(llb,rrb);
    return gcd2(r->getGCD(llb,rrb),l->getGCD(llb,rrb));
  }

  void ch(int x, ll va){
    if(rb < x || lb > x)return;
    if(rb == x && lb == x){
      val = va;
      return;
    }
    int mid = (lb+rb)>>1;
    if(mid >= x){
      if(l == NULL)exl();
      l->ch(x,va);
      if(r == NULL)val = l->val;
      else val = gcd2(l->val,r->val);
    }
    else{
      if(r == NULL)exr();
      r->ch(x,va);
      if(l == NULL)val = r->val;
      else val = gcd2(l->val,r->val);
    }
  }
  void chno(seg1d *a, seg1d *b, int x){
    if(rb < x || lb > x)return;
    int mid = (lb+rb)>>1;
    if(mid >= x){
      if(a == NULL){
        val = b->val;
        if(rb == lb)return;
        if(l == NULL)exl();
        l->chno(a,b->l,x);
        return;
      }
      if(b == NULL){
        val = a->val;
        if(rb == lb)return;
        if(l == NULL)exl();
        l->chno(a->l,b,x);
        return;
      }
      val = gcd2(a->val,b->val);
      if(rb == lb)return;
      if(l == NULL)exl();
      l->chno(a->l,b->l,x);
    }
    else{
      if(a == NULL){
        val = b->val;
        if(rb == lb)return;
        if(r == NULL)exr();
        r->chno(a,b->r,x);
        return;
      }
      if(b == NULL){
        val = a->val;
        if(rb == lb)return;
        if(r == NULL)exr();
        r->chno(a->r,b,x);
        return;
      }
      val = gcd2(a->val,b->val);
      if(rb == lb)return;
      if(r == NULL)exr();
      r->chno(a->r,b->r,x);
    }
  }
};

struct seg2d{

  int lb, rb;

  seg2d *l, *r;
  seg1d *c;

  seg2d () : l(NULL), r(NULL), c(NULL) {}

  inline void init(int lx, int rx){
    lb = lx, rb = rx;
  }

  inline void exl(){
    int mid = (lb+rb)>>1;
    l = new seg2d;
    l->init(lb,mid);
  }
  inline void exr(){
    int mid = (lb+rb)>>1;
    r = new seg2d;
    r->init(mid+1,rb);
  }
  inline void exc(){
    c = new seg1d;
    c->init(0, mxN);
  }

  ll getGCD(int llb, int rrb, int uub, int ddb){
    if(llb > rb || rrb < lb)return 0;
    if(llb <= lb && rrb >= rb){
      if(c == NULL)return 0;
      return c->getGCD(uub,ddb);
    }
    if((l == NULL && r == NULL) || c == NULL)return 0;
    if(r == NULL)return l->getGCD(llb,rrb,uub,ddb);
    if(l == NULL)return r->getGCD(llb,rrb,uub,ddb);
    return gcd2(r->getGCD(llb,rrb,uub,ddb),l->getGCD(llb,rrb,uub,ddb));
  }

  void ch(int x, int y, ll val){
    if(rb < x || lb > x)return;
    if(rb == x && lb == x){if(c == NULL)exc();c->ch(y,val);return;}
    int mid = (rb+lb)>>1;
    if(mid >= x){
      if(l == NULL)exl();
      if(c == NULL)exc();
      l->ch(x,y,val);
      if(r == NULL){
        exr();
      }
      c->chno(l->c,r->c,y);
    }
    else{
      if(r == NULL)exr();
      if(c == NULL)exc();
      r->ch(x,y,val);
      if(l == NULL){
        exl();
      }
      c->chno(l->c,r->c,y);
    }
  }	
};

seg2d root;

void init(int R, int C) {
  root.init(0,mxN);
}

void update(int P, int Q, long long K) {
  root.ch(P+1,Q+1,K);
}

long long calculate(int P, int Q, int U, int V) {
  return root.getGCD(P+1,U+1,Q+1,V+1);
}

Compilation message (stderr)

game.cpp: In constructor 'seg1d::seg1d()':
game.cpp:25:14: warning: 'seg1d::r' will be initialized after [-Wreorder]
   25 |   seg1d *l, *r;
      |              ^
game.cpp:23:6: warning:   'll seg1d::val' [-Wreorder]
   23 |   ll val;
      |      ^~~
game.cpp:27:3: warning:   when initialized here [-Wreorder]
   27 |   seg1d () : l(NULL), r(NULL), val(0) {}
      |   ^~~~~

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