Submission #593059

#	Time	Username	Problem	Language	Result	Execution time	Memory
593059		MilosMilutinovic	Game (IOI13_game)	C++14	100 / 100	2630 ms	73184 KiB

game

/**
 *    author:  wxhtzdy
 *    created: 10.07.2022 09:47:45
**/

// learning 2d segment tree of treaps from USACO Guide

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

using namespace std;

mt19937 rng(time(0));

struct TreapNode {
  TreapNode *l, *r;
  int pos, key, mn, mx;
  long long val, g;

  TreapNode(int position, long long value) {
    l = r = nullptr;
    mn = mx = pos = position;
    key = rng();
    val = g = value;
  }

  void update() {
    g = val;
    if (l) g = __gcd(g, l->g);
    if (r) g = __gcd(g, r->g);
    mn = (l ? l->mn : pos);
    mx = (r ? r->mx : pos);
  }
};

struct Treap {
  TreapNode *root;

  Treap() {
    root = nullptr;
  }
  
  void split(TreapNode *t, int pos, TreapNode *&l, TreapNode *&r) {
    if (t == nullptr) {
      l = r = nullptr;
      return;
    }       
    if (t->pos < pos) {
      split(t->r, pos, l, r);
      t->r = l;
      l = t;
    } else {
      split(t->l, pos, l, r);
      t->l = r;
      r = t;
    }
    t->update();
  }

  TreapNode* merge(TreapNode *l, TreapNode *r) {
    if (!l) return r;
    if (!r) return l;
    if (l->key < r->key) {
      l->r = merge(l->r, r);
      l->update();
      return l;
    } else {
      r->l = merge(l, r->l);
      r->update();
      return r;
    }
  }

  bool find(int pos) {
    TreapNode *t = root;
    while (t) {
      if (t->pos == pos) return true;
      if (t->pos > pos) t = t->l;
      else t = t->r;
    }
    return false;
  }

  void update(TreapNode *t, int pos, long long value) {
    if (t->pos == pos) {
      t->val = value;
      t->update();
      return;
    }

    if (t->pos > pos) {
      update(t->l, pos, value);
    } else {
      update(t->r, pos, value);
    }
    t->update();
  }

  void insert(int pos, long long value) {
    if (find(pos)) {
      update(root, pos, value);
      return;
    }
    TreapNode *l, *r;
    split(root, pos, l, r);
    root = merge(merge(l, new TreapNode(pos, value)), r);
  }
  
  long long query(TreapNode *t, int l, int r) {
    if (t->mx < l || t->mn > r) return 0LL;
    if (l <= t->mn && t->mx <= r) return t->g;
    long long res = 0;
    if (l <= t->pos && t->pos <= r) {
      res = t->val;
    }
    if (t->l) res = __gcd(res, query(t->l, l, r));
    if (t->r) res = __gcd(res, query(t->r, l, r));
    return res;
  }   

  long long query(int l, int r) {
    if (!root) return 0LL;
    return query(root, l, r);
  }
};

struct Segtree {
  Segtree *l, *r;
  Treap treap;
  int lo, hi;

  Segtree () { l = r = nullptr; }
  Segtree(int st, int en) {
    l = r = nullptr;
    lo = st;
    hi = en;
  }

  void new_left() {
    if (!l) {
      l = new Segtree(lo, (lo + hi) / 2);
    }
  }
  void new_right() {
    if (!r) {
      r = new Segtree((lo + hi) / 2 + 1, hi);
    }
  }

  void fix(int pos) {
    long long val = 0;
    if (l) val = __gcd(val, l->treap.query(pos, pos));
    if (r) val = __gcd(val, r->treap.query(pos, pos)); 
    treap.insert(pos, val);
  }

  void update(int x, int y, long long val) {
    if (hi < x || lo > x) return;
    if (lo == hi) {
      treap.insert(y, val);
      return;
    }
    int mid = (lo + hi) / 2;
    if (x <= mid) {
      new_left();
      l->update(x, y, val);
    } else {
      new_right();
      r->update(x, y, val);
    }
    fix(y);
  }
   
  long long query(int t, int b, int st, int en) {
    if (hi < t || lo > b) return 0LL;
    if (t <= lo && hi <= b) return treap.query(st, en);
    long long ans = 0;
    if (l) ans = __gcd(ans, l->query(t, b, st, en));
    if (r) ans = __gcd(ans, r->query(t, b, st, en));
    return ans;
  }
};

Segtree segtree;

void init(int R, int C) {
  segtree = Segtree(0, R - 1);
}

void update(int P, int Q, long long K) {
  segtree.update(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
  return segtree.query(P, U, Q, V);
}

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