Submission #1014568

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014568		huutuan	Game (IOI13_game)	C++14	63 / 100	791 ms	256000 KiB

game

#include "game.h"

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;
}

#include <bits/stdc++.h>

using namespace std;

int R, C;

struct Node{
   long long val;
   Node *l;
   Node *r;
   Node (){
      val=0;
      l=nullptr;
      r=nullptr;
   }
};

struct SegmentTree{
   Node *root;
   SegmentTree *l;
   SegmentTree *r;
   SegmentTree(){
      root=new Node();
      l=nullptr;
      r=nullptr;
   }
   void update(Node *t, Node *tl, Node *tr, int l, int r, int pos, long long val, bool sussy){
      if (l==r){
         if (sussy) t->val=gcd2(tl?tl->val:0, tr?tr->val:0);
         else t->val=val;
         return;
      }
      if (!t->l) t->l=new Node();
      if (!t->r) t->r=new Node();
      int mid=(l+r)>>1;
      if (pos<=mid) update(t->l, tl?tl->l:nullptr, tr?tr->l:nullptr, l, mid, pos, val, sussy);
      else update(t->r, tl?tl->r:nullptr, tr?tr->r:nullptr, mid+1, r, pos, val, sussy);
      t->val=gcd2(t->l->val, t->r->val);
   }
   long long get(Node *t, int l, int r, int L, int R){
      if (r<L || R<l) return 0;
      if (L<=l && r<=R) return t->val;
      if (!t->l || !t->r) return 0;
      int mid=(l+r)>>1;
      return gcd2(get(t->l, l, mid, L, R), get(t->r, mid+1, r, L, R));
   }
};

struct SegmentTree2d{
   SegmentTree *root;
   SegmentTree2d(){
      root=new SegmentTree();
   }
   void update(SegmentTree *t, int l, int r, int x, int y, long long val){
      if (l!=r){
         int mid=(l+r)>>1;
         if (!t->l) t->l=new SegmentTree();
         if (!t->r) t->r=new SegmentTree();
         if (x<=mid) update(t->l, l, mid, x, y, val);
         else update(t->r, mid+1, r, x, y, val);
      }
      t->update(t->root, t->l?t->l->root:nullptr, t->r?t->r->root:nullptr, 1, C, y, val, l!=r);
   }
   long long get(SegmentTree *t, int l, int r, int lx, int rx, int ly, int ry){
      if (rx<l || r<lx) return 0;
      if (lx<=l && r<=rx) return t->get(t->root, 1, C, ly, ry);
      if (!t->l || !t->r) return 0;
      int mid=(l+r)>>1;
      return gcd2(get(t->l, l, mid, lx, rx, ly, ry), get(t->r, mid+1, r, lx, rx, ly, ry));
   }
} st;

int sz;
long long t[8010][8010];

long long sum_y(int vx, int vy, int tly, int try_, int ly, int ry) {
   if (ly > ry) 
      return 0;
   if (ly == tly && try_ == ry)
      return t[vx][vy];
   int tmy = (tly + try_) >> 1;
   return gcd2(sum_y(vx, vy<<1, tly, tmy, ly, min(ry, tmy)),
      sum_y(vx, vy<<1|1, tmy+1, try_, max(ly, tmy+1), ry));
}

long long sum_x(int vx, int tlx, int trx, int lx, int rx, int ly, int ry) {
   if (lx > rx)
      return 0;
   if (lx == tlx && trx == rx)
      return sum_y(vx, 1, 1, C, ly, ry);
   int tmx = (tlx + trx) >> 1;
   return gcd2(sum_x(vx<<1, tlx, tmx, lx, min(rx, tmx), ly, ry),
      sum_x(vx<<1|1, tmx+1, trx, max(lx, tmx+1), rx, ly, ry));
}

void update_y(int vx, int lx, int rx, int vy, int ly, int ry, int x, int y, long long new_val) {
   if (ly == ry) {
      if (lx == rx)
         t[vx][vy] = new_val;
      else
         t[vx][vy] = gcd2(t[vx<<1][vy], t[vx<<1|1][vy]);
   } else {
      int my = (ly + ry) >> 1;
      if (y <= my)
         update_y(vx, lx, rx, vy<<1, ly, my, x, y, new_val);
      else
         update_y(vx, lx, rx, vy<<1|1, my+1, ry, x, y, new_val);
      t[vx][vy] = gcd2(t[vx][vy<<1], t[vx][vy<<1|1]);
   }
}

void update_x(int vx, int lx, int rx, int x, int y, long long new_val) {
   if (lx != rx) {
      int mx = (lx + rx) >> 1;
      if (x <= mx)
         update_x(vx<<1, lx, mx, x, y, new_val);
      else
         update_x(vx<<1|1, mx+1, rx, x, y, new_val);
   }
   update_y(vx, lx, rx, 1, 1, C, x, y, new_val);
}

void init(int _R, int _C) {
   R=_R; C=_C;
}

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

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

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