Submission #898209

#	Time	Username	Problem	Language	Result	Execution time	Memory
898209		KaleemRazaSyed	Game (IOI13_game)	C++17	0 / 100	1 ms	604 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;
    lc = rc = NULL;
  }

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

    int mid = (s + e) / 2;
    if(lc == NULL and p < mid)
      lc = new node(s, mid);
    else if(rc == NULL and mid <= p)
      rc = new node(mid, e);
    gc = 0;
    if(lc != NULL)
      lc -> update(p, K), gc = gcd(gc, lc -> gc);
    if(rc != NULL)
      rc -> update(p, K), gc = gcd(gc, rc -> gc);
  }

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

int sz;
struct Segnode
{
  int s, e;
  node *tree;
  Segnode *lc, *rc;
  Segnode(int S, int E) {
    s = S, e = E;
    lc = rc = NULL;
    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;
    }
    
    int mid = (s + e) / 2;
    if(lc == NULL and p < mid)
      lc = new Segnode(s, mid);
    if(rc == NULL and p >= mid)
      rc = new Segnode(mid, e);

    if(lc != NULL)
      lc -> update(p, p2, K);
    if(rc != NULL)
      rc -> update(p, p2, K);

    int p21 = p2 + 1;
    ll g1 = 0;
    if(lc != NULL) g1 = lc -> tree -> get(p2, p21);
    ll g2 = 0;
    if(rc != NULL) g2 = rc -> tree -> get(p2, p21);
    g1 = gcd(g1, g2);
    tree -> update(p2, g1);
  }

  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);
    ll g = 0;
    if(lc != NULL)
      g = lc -> get(lx, rx, ly, ry);
    if(rc != NULL)
      g = gcd(g, rc -> get(lx, ly, rx, ry));
    return g;
  }
};

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

/*
#define MAX_SIZE 1000000000
#define MAX_N 272000
 
int main() {
    int R, C, N;
    int P, Q, U, V;
    long long K;
    int i, type;
 
    assert(scanf("%d", &R) == 1);
    assert(scanf("%d", &C) == 1);
    assert(scanf("%d", &N) == 1);
 
    init(R, C);
    std::vector<long long> answers;
 
    for (i = 0; i < N; i++) {
        assert(scanf("%d", &type) == 1);
        if (type == 1) {
            assert(scanf("%d%d%lld", &P, &Q, &K) == 3);
            update(P, Q, K);
        } else if (type == 2) {
            assert(scanf("%d%d%d%d", &P, &Q, &U, &V) == 4);
            answers.push_back(calculate(P, Q, U, V));
        } 
    }
    for (auto answer: answers) {
      printf("%lld\n", answer);
    }
 
    return 0;
}
 
//*/

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