Submission #258455

#	Time	Username	Problem	Language	Result	Execution time	Memory
258455		sandoval	Game (IOI13_game)	C++11	63 / 100	2227 ms	35520 KiB

game

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

using namespace std;
using ii = pair<int,int>;
using ll = long long;

constexpr int MAXN = 5 + 2000;

ll gcd(ll a, ll b) {
  return b ? gcd(b, a%b) : a;
}

struct segtree {
#define m ((s+e)/2)
struct Node {
  ll val;
  Node* l, *r;
  Node() : val(0), l(nullptr), r(nullptr) {}
};
Node* root = new Node();
segtree() = default;
ll query(int s, int e, Node* curr, int l, int r) {
  if (l > r || curr == nullptr) return 0;
  if (s == l && e == r) return curr->val;
  return gcd(query(s, m, curr->l, l, min(m,r)), query(1+m, e, curr->r, max(1+m,l), r));
}
void update(int s, int e, Node* curr, int l, int r, ll add) {
  if (l > r) return;
  if (s == l && e == r) {
    curr->val = add;
  } else {
    if (curr->l == nullptr) curr->l = new Node();
    if (curr->r == nullptr) curr->r = new Node();
    update(s, m, curr->l, l, min(m,r), add);
    update(1+m, e, curr->r, max(1+m,l), r, add);
    curr->val = gcd(curr->l->val, curr->r->val);
  }
}};

namespace input {int R,C;}

namespace stree2d {
segtree t[4*MAXN];
ll query(int s, int e, int p, int l, int r, int sy, int ey) {
  if (l > r) return 0;
  if (s == l && e == r) return t[p].query(1, input::C, t[p].root, sy, ey);
  ll le = query(s, m, 2*p, l, min(m,r), sy, ey);
  ll ri = query(1+m, e, 1+2*p, max(1+m,l), r, sy, ey);
  return gcd(le,ri);
}
void update(int s, int e, int p, int l, int r, int sy, int ey, ll add) {
  if (l > r) return;
  if (s == l && e == r) {
    t[p].update(1, input::C, t[p].root, sy, ey, add);
  } else {
    update(s, m, 2*p, l, min(m,r), sy, ey, add);
    update(1+m, e, 1+2*p, max(1+m,l), r, sy, ey, add);
    ll newval = gcd(t[2*p].query(1, input::C, t[2*p].root, sy, ey),
           t[1+2*p].query(1, input::C, t[1+2*p].root, sy, ey));
    t[p].update(1, input::C, t[p].root, sy, sy, newval);
  }
}}

int subtask=-1;
void init(int R, int C) {
  if (R <= 10 && C <= 100000) { // subtask 2.
    subtask = 2;
  } else { // subtask 1 & 3.
    subtask = 3;
  }
  input::R = R;
  input::C = C;
}

segtree s2[11];

void update(int P, int Q, long long K) {
  if (subtask == -1) return;
  ++P; ++Q;
  if (subtask == 2) { // 10 segment trees.
    s2[P].update(1, input::C, s2[P].root, Q, Q, K);
  } else { // un solo segtree 2d.
    assert(subtask == 3);
    stree2d::update(1, input::R, 1, P, P, Q, Q, K);
  }
}

long long calculate(int P, int Q, int U, int V) {
  ++P; ++Q; ++U; ++V;
  if (subtask == 2) {
    long long ans = 0;
    for (int i = P; i <= U; ++i) {
      ans = gcd(ans, s2[i].query(1, input::C, s2[i].root, Q, V));
    }
    return ans;
  } else {
    assert(subtask == 3);
    assert(P >= 1 && P <= input::R);
    assert(U >= 1 && U <= input::R);
    assert(P <= U);

    assert(Q >= 1 && Q <= input::C);
    assert(V >= 1 && V <= input::C);
    assert(Q <= V);
    return stree2d::query(1, input::R, 1, P, U, Q, V);
  }
  return 0LL;
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

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