Submission #956452

#	Time	Username	Problem	Language	Result	Execution time	Memory
956452		abczz	Game (IOI13_game)	C++14	80 / 100	2472 ms	256000 KiB

game

#include "game.h"
#include <iostream>
#include <vector>
#include <numeric>
#define ll long long
 
using namespace std;
 
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 (y <= mid) {
      int tmp = st[id].chl;
      updateC(tmp, (idl != -1 ? st[idl].chl : -1), (idr != -1 ? st[idr].chl : -1), l, mid, y, w);
      st[id].chl = tmp;
    }
    else {
      int tmp = st[id].chr;
      updateC(tmp, (idl != -1 ? st[idl].chr : -1), (idr != -1 ? st[idr].chr : -1), mid+1, r, y, w);
      st[id].chr = tmp;
    }
    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;
    }
    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: 0 / 20