Submission #956472

#	Time	Username	Problem	Language	Result	Execution time	Memory
956472		abczz	Game (IOI13_game)	C++14	100 / 100	2833 ms	63908 KiB

game

#include "game.h"
#include <iostream>
#include <vector>
#include <numeric>
#define ll long long
 
using namespace std;

ll A[22000], sz;
ll gcd(ll a, ll b) {
  if (!b) return a;
  else if (!a) return b;
  else return gcd(b%a, a);
}
struct SegTree{
  struct Node{
    ll val;
    int chl;
    int chr;
  };
  int cnt = 0;
  Node st[20000000];
  void get(int &id) {
    if (id != -1) return;
    st[cnt] = {0, -1, -1};
    id = cnt++;
  }
  void updateC(int &id, int idl, int idr, int l, int r, int y, ll w) {
    get(id);
    if (l == r) {
      if (idl == -1 && idr == -1) st[id].val = w;
      else st[id].val = gcd((idl != -1 ? st[idl].val : 0), (idr != -1 ? st[idr].val : 0));
      return;
    }
    int mid = (l+r)/2;
    if (st[id].chr == -1e9) {
      int ty = st[id].chl;
      ll tw = st[id].val;
      st[id] = {0, -1, -1};
      if (ty <= mid) {
        int tmp = st[id].chl, tmpchl = (idl != -1 ? st[idl].chl : -1), tmpchr = (idr != -1 ? st[idr].chl : -1);
        if (idl != -1 && st[idl].chr == -1e9) {
          if (st[idl].chl <= mid) tmpchl = idl;
          else tmpchl = -1;
        }
        if (idr != -1 && st[idr].chr == -1e9) {
          if (st[idr].chl <= mid) tmpchr = idr;
          else tmpchr = -1;
        }
        updateC(tmp, tmpchl, tmpchr, l, mid, ty, tw);
        st[id].chl = tmp;
      }
      else {
        int tmp = st[id].chr, tmpchl = (idl != -1 ? st[idl].chr : -1), tmpchr = (idr != -1 ? st[idr].chr : -1);
        if (idl != -1 && st[idl].chr == -1e9) {
          if (st[idl].chl > mid) tmpchl = idl;
          else tmpchl = -1;
        }
        if (idr != -1 && st[idr].chr == -1e9) {
          if (st[idr].chl > mid) tmpchr = idr;
          else tmpchr = -1;
        }
        updateC(tmp, tmpchl, tmpchr, mid+1, r, ty, tw);
        st[id].chr = tmp;
      }
    }
    else if (id + 1 == cnt) {
      st[id].val = w;
      st[id].chl = y;
      st[id].chr = -1e9;
      return;
    }
    if (y <= mid) {
      int tmp = st[id].chl, tmpchl = (idl != -1 ? st[idl].chl : -1), tmpchr = (idr != -1 ? st[idr].chl : -1);
      if (idl != -1 && st[idl].chr == -1e9) {
        if (st[idl].chl <= mid) tmpchl = idl;
        else tmpchl = -1;
      }
      if (idr != -1 && st[idr].chr == -1e9) {
        if (st[idr].chl <= mid) tmpchr = idr;
        else tmpchr = -1;
      }
      updateC(tmp, tmpchl, tmpchr, l, mid, y, w);
      st[id].chl = tmp;
    }
    else {
      int tmp = st[id].chr, tmpchl = (idl != -1 ? st[idl].chr : -1), tmpchr = (idr != -1 ? st[idr].chr : -1);
      if (idl != -1 && st[idl].chr == -1e9) {
        if (st[idl].chl > mid) tmpchl = idl;
        else tmpchl = -1;
      }
      if (idr != -1 && st[idr].chr == -1e9) {
        if (st[idr].chl > mid) tmpchr = idr;
        else tmpchr = -1;
      }
      updateC(tmp, tmpchl, tmpchr, mid+1, r, y, w);
      st[id].chr = tmp;
    }
    //cout << id << " " << st[id].chl << " " << st[id].chr << endl;
    st[id].val = gcd((st[id].chl != -1 ? st[st[id].chl].val : 0), (st[id].chr != -1 ? st[st[id].chr].val : 0));
  }
  void updateR(int &id, int l, int r, int x, int y, ll w) {
    get(id);
    if (id+1 == cnt) {
      int tmp = -1;
      get(tmp);
    }
    int tmp = id+1;
    if (l == r) {
      updateC(tmp, -1, -1, 0, (int)1e9-1, y, w);
      st[id].val = st[id+1].val;
      return;
    }
    int mid = (l+r)/2;
    if (x <= mid) {
      int tmp = st[id].chl;
      updateR(tmp, l, mid, x, y, w);
      st[id].chl = tmp;
    }
    else {
      int tmp = st[id].chr;
      updateR(tmp, mid+1, r, x, y, w);
      st[id].chr = tmp;
    }
    updateC(tmp, (st[id].chl != -1 ? st[id].chl+1 : -1), (st[id].chr != -1 ? st[id].chr+1 : -1), 0, (ll)1e9-1, y, w);
    st[id].val = gcd((st[id].chl != -1 ? st[st[id].chl].val : 0), (st[id].chr != -1 ? st[st[id].chr].val : 0));
  }
  ll queryC(int id, int l, int r, int ql, int qr) {
    if (id == -1 || qr < l || r < ql) return 0;
    else if (ql <= l && r <= qr) {
      return st[id].val;
    }
    if (st[id].chr == -1e9) {
      if (ql <= st[id].chl && st[id].chl <= qr) return st[id].val;
      else return 0;
    }
    int mid = (l+r)/2;
    return gcd(queryC(st[id].chl, l, mid, ql, qr), queryC(st[id].chr, mid+1, r, ql, qr));
  }
  ll queryR(int id, int l, int r, int ql, int qr, int qx, int qy) {
    if (id == -1 || qr < l || r < ql) return 0;
    else if (ql <= l && r <= qr) return queryC(id+1, 0, (int)1e9-1, qx, qy);
    int mid = (l+r)/2;
    return gcd(queryR(st[id].chl, l, mid, ql, qr, qx, qy), queryR(st[id].chr, mid+1, r, ql, qr, qx, qy));
  }
}ST;
 
void init(int R, int C) {
  int rt = -1;
  ST.get(rt);
}
 
void update(int P, int Q, long long K) {
  int rt = 0;
  ST.updateR(rt, 0, (int)1e9-1, P, Q, K);
}
 
long long calculate(int P, int Q, int U, int V) {
  int rt = 0;
  return ST.queryR(rt, 0, (int)1e9-1, P, U, Q, V);
}

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