Submission #1016002

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016002		huutuan	Game (IOI13_game)	C++14	80 / 100	2248 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;
   int il, ir;
   Node (){
      val=0;
      il=0, ir=0;
   }
};

struct SegmentTree{
   vector<Node> t;
   int il, ir;
   SegmentTree(){
      t.emplace_back();
      il=0, ir=0;
   }
};

struct SegmentTree2d{
   vector<SegmentTree> t;
   SegmentTree2d(){
      t.emplace_back();
   }
   void update1(int k, int l, int r, int x, int y, long long val){
      if (l!=r){
         int mid=(l+r)>>1;
         if (x<=mid){
            if (!t[k].il){
               t[k].il=t.size();
               t.emplace_back();
            }
            update1(t[k].il, l, mid, x, y, val);
         }else{
            if (!t[k].ir){
               t[k].ir=t.size();
               t.emplace_back();
            }
            update1(t[k].ir, mid+1, r, x, y, val);
         }
      }
      update2(k, 0, 1, 1e9, y, val, l!=r);
   }
   long long get1(int k, 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 get2(k, 0, 1, 1e9, ly, ry);
      int mid=(l+r)>>1;
      return gcd2(t[k].il?get1(t[k].il, l, mid, lx, rx, ly, ry):0, t[k].ir?get1(t[k].ir, mid+1, r, lx, rx, ly, ry):0);
   }
   void update2(int id, int k, int l, int r, int pos, long long val, bool sussy){
      if (l==r){
         if (sussy) t[id].t[k].val=gcd2(t[id].il?get2(t[id].il, 0, 1, 1e9, pos, pos):0, t[id].ir?get2(t[id].ir, 0, 1, 1e9, pos, pos):0);
         else t[id].t[k].val=val;
         return;
      }
      int mid=(l+r)>>1;
      if (pos<=mid){
         if (!t[id].t[k].il){
            t[id].t[k].il=t[id].t.size();
            t[id].t.emplace_back();
         }
         update2(id, t[id].t[k].il, l, mid, pos, val, sussy);
      }else{
         if (!t[id].t[k].ir){
            t[id].t[k].ir=t[id].t.size();
            t[id].t.emplace_back();
         }
         update2(id, t[id].t[k].ir, mid+1, r, pos, val, sussy);
      }
      t[id].t[k].val=gcd2(t[id].t[k].il?t[id].t[t[id].t[k].il].val:0, t[id].t[k].ir?t[id].t[t[id].t[k].ir].val:0);
   }
   long long get2(int id, int k, int l, int r, int L, int R){
      if (r<L || R<l) return 0;
      if (L<=l && r<=R) return t[id].t[k].val;
      int mid=(l+r)>>1;
      return gcd2(t[id].t[k].il?get2(id, t[id].t[k].il, l, mid, L, R):0, t[id].t[k].ir?get2(id, t[id].t[k].ir, mid+1, r, L, R):0);
   }
} st;

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

void update(int P, int Q, long long K) {
   ++P; ++Q;
   st.update1(0, 1, 1e9, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
   ++P; ++Q; ++U; ++V;
   return st.get1(0, 1, 1e9, P, U, Q, V);
}

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