Submission #898181

#	Time	Username	Problem	Language	Result	Execution time	Memory
898181		Faisal_Saqib	Game (IOI13_game)	C++17	63 / 100	1394 ms	256000 KiB

game

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

using namespace std;

#define ll long long

struct node
{
  int s, e;
  ll gc;
  node *lc, *rc;
  node(int S, int E) {
    s = S, e = E, gc = 0;
  }

  void update(int p, ll K)
  {
    if(p < s || e <= p) return;
    if(e - s == 1) {
      	gc = K;
      	return;
      }

    if(lc == NULL) {
	int mid = (s + e) / 2;
	lc = new node(s, mid);
	rc = new node(mid, e);
      }

    lc -> update(p, K);
    rc -> update(p, K);
    gc = gcd(lc -> gc, rc -> gc);
  }

  ll get(int l, int r)
  {
    if(r <= s || e <= l) return 0;
    if(l <= s && e <= r) return gc;
    if(lc == NULL) return 0;
    return gcd(lc -> get(l, r), rc -> get(l, r));
  }
};

int sz;
struct Segnode
{
  int s, e;
  node *tree;
  Segnode *lc, *rc;
  Segnode(int S, int E) {
    s = S, e = E;
    tree = new node(0, sz);
  }

  void update(int p, int p2, ll K)
  {
    if(p < s || e <= p) return;
    if(e - s == 1){
      tree->update(p2, K);
      return;
    }
    
    if(lc == NULL) {
      int mid = (s + e) / 2;
      lc = new Segnode(s, mid);
      rc = new Segnode(mid, e);
    }

    lc -> update(p, p2, K);
    rc -> update(p, p2, K);

    ll g1 = lc -> tree -> get(p2, p2 + 1), g2 = rc -> tree -> get(p2, p2 + 1);
    tree -> update(p2, gcd(g1, g2));
  }

  ll get(int lx, int rx, int ly, int ry)
  {
    if(rx <= s || e <= lx) return 0;
    if(lx <= s && e <= rx)
      return tree->get(ly, ry);
    if(lc == NULL) return 0;
    return gcd(lc -> get(lx, rx, ly, ry),
	       rc -> get(lx, rx, ly, ry));
  }
};

Segnode* tree;

void init(int R, int C)
{
  sz = C;
  tree = new Segnode(0, R);
}

void update(int p, int q, ll K)
{
  tree->update(p, q, K); 
}

ll calculate(int lx, int ly, int rx, int ry)
{
  rx ++ , ry++;
  return tree->get(lx, rx, ly, ry);
}

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