Submission #1303306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303306		DeltaStruct	Game (IOI13_game)	C++20	0 / 100	1 ms	572 KiB

game

#include <bits/stdc++.h>
using namespace std;
#include "game.h"

long long res;
struct node {
  node *lp,*rp; long long x;
  node() : lp(nullptr),rp(nullptr),x(0) {}
  long long update(int i,long long y,int ll,int rr){
    if (i<ll||rr<=i) return x;
    if (ll+1==rr) return x = gcd(x,y);
    if (lp==nullptr) lp = new node();
    if (rp==nullptr) rp = new node();
    return x = gcd(lp->update(i,y,ll,(ll+rr)/2),rp->update(i,y,(ll+rr)/2,rr));
  }
  void query(int l,int r,int ll,int rr){
    if (r<=ll||rr<=l) return;
    if (l<=ll&&rr<=r) return (void)(res = gcd(res,x));
    if (lp!=nullptr) lp->query(l,r,ll,(ll+rr)/2);
    if (rp!=nullptr) rp->query(l,r,(ll+rr)/2,rr);
  }
};

int h,w;
struct nnode {
  nnode *lp,*rp; node x;
  nnode() : lp(nullptr),rp(nullptr),x() {}
  void update(int i,int k,long long y,int ll,int rr){
    if (i<ll||rr<=i) return;
    x.update(k,y,0,w);
    if (ll+1==rr) return;
    if (lp==nullptr) lp = new nnode();
    if (rp==nullptr) rp = new nnode();
    lp->update(i,k,y,ll,(ll+rr)/2),rp->update(i,k,y,(ll+rr)/2,rr);
  }
  void query(int l,int r,int i,int k,int ll,int rr){
    if (r<=ll||rr<=l) return;
    if (l<=ll&&rr<=r) return (void)x.query(i,k,0,w);
    if (lp!=nullptr) lp->query(l,r,i,k,ll,(ll+rr)/2);
    if (rp!=nullptr) rp->query(l,r,i,k,(ll+rr)/2,rr);
  }
};
nnode segtree;

void init(int H,int W){
  h = H,w = W;
}

void update(int i,int k,long long x){
  segtree.update(i,k,x,0,h);
}

long long calculate(int a,int b,int c,int d){
  res = 0,segtree.query(a,c+1,b,d+1,0,h);
  return res;
}

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