Submission #587411

#	Time	Username	Problem	Language	Result	Execution time	Memory
587411		FatihSolak	Game (IOI13_game)	C++17	10 / 100	13099 ms	4732 KiB

game

#include "game.h"
#include <bits/stdc++.h>
#define CNT (int)2e7
#define CNT2 (int)1e6
using namespace std;
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;
}
struct node{
  int l = 0,r = 0;
  long long val = 0;
}nodes[CNT];
int cnt = 1;
struct SegTree{
  int root = -1;
  void upd(int v,int tl,int tr,int pos,long long val){
    if(tl == tr){
      nodes[v].val = val;
      return;
    }
    int tm = (tl + tr)/2;
    if(pos <= tm){
      if(nodes[v].l == 0)
        nodes[v].l = cnt++;
      upd(nodes[v].l,tl,tm,pos,val);
    }
    else{
      if(nodes[v].r == 0)
        nodes[v].r = cnt++;
      upd(nodes[v].r,tm+1,tr,pos,val);
    }
    nodes[v].val = __gcd(nodes[nodes[v].l].val,nodes[nodes[v].r].val);
  }
  long long get(int v,int tl,int tr,int l,int r){
    if(v == 0 || tr < l || r < tl)
      return 0;
    if(l <= tl && tr <= r){
      return nodes[v].val;
    }
    int tm = (tl + tr)/2;
    return __gcd(get(nodes[v].l,tl,tm,l,r),get(nodes[v].r,tm+1,tr,l,r));
  }
  void upd(int pos,long long val){
    if(root == -1)
      root = cnt++;
    upd(root,1,1e9,pos,val);
  }
  long long get(int l,int r){
    if(root == -1)
      return 0;
    return get(root,1,1e9,l,r);
  }
};
map<int,int> mp;
int cntmp = 1;
SegTree numbers[22005];
struct node2{
  int l = 0,r = 0;
  SegTree val;
}nodes2[CNT2];
int cnt2 = 1;
struct SegTree2D{
  int root = -1;
  void upd(int v,int tl,int tr,int x,int y,long long val){
    nodes2[v].val.upd(y,numbers[mp[y]].get(tl,tr));
    if(tl == tr){
      return;
    }
    int tm = (tl + tr)/2;
    if(x <= tm){
      if(nodes2[v].l == 0)
        nodes2[v].l = cnt2++;
      upd(nodes2[v].l,tl,tm,x,y,val);
    }
    else{
      if(nodes2[v].r == 0)
        nodes2[v].r = cnt2++;
      upd(nodes2[v].r,tm+1,tr,x,y,val);
    }
  }
  long long get(int v,int tl,int tr,int l,int r,int l2,int r2){
    if(v == 0 || tr < l || r < tl)
      return 0;
    if(l <= tl && tr <= r){
      return nodes2[v].val.get(l2,r2);
    }
    int tm = (tl + tr)/2;
    return __gcd(get(nodes2[v].l,tl,tm,l,r,l2,r2),get(nodes2[v].r,tm+1,tr,l,r,l2,r2));
  }
  void upd(int x,int y,long long val){
    if(root == -1)
      root = cnt2++;
    upd(root,1,1e9,x,y,val);
  }
  long long get(int l,int r,int l2,int r2){
    if(root == -1)
      root = cnt2++;
    return get(root,1,1e9,l,r,l2,r2);
  }
}tree;
int p1[22005],p2[22005];
long long p3[22005];
int sz = 0;
void init(int R, int C) {
  //tree.init(R,C);
}
int update_cnt = 0;
int limit = 0;
void update(int P, int Q, long long K) {
  P++,Q++;
  update_cnt++;
  bool ok = 1;
  for(int i = 0;i<sz;i++){
    if(p1[i] == P && p2[i] == Q){
      p3[i] = K;
      ok = 0;
    }
  }
  if(ok){
    p1[sz] = P;
    p2[sz] = Q;
    p3[sz] = K;
    sz++;
  }
  if(update_cnt <= limit){
    if(mp[Q] == 0){
      mp[Q] =  cntmp++;
    }
    numbers[mp[Q]].upd(P,K);
    tree.upd(P,Q,K);
  }

}

long long calculate(int P, int Q, int U, int V) {
  P++,Q++,U++,V++;
  assert(cnt < CNT);
  assert(cnt2 < CNT2);
  if(update_cnt <= limit)
    return tree.get(P,U,Q,V);
  long long g = 0;
  for(int i = 0;i<sz;i++){
    if(P <= p1[i] && p1[i] <= U && Q <= p2[i] && p2[i] <= V){
      g = __gcd(g,p3[i]);
    }
  }
  return g;
}

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