제출 #258459

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
258459		sandoval	게임 (IOI13_game)	C++11	63 / 100	1736 ms	256004 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;
}

#define m ((s+e)/2)
struct segtree {
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 {
struct Node2d {
  segtree t;
  Node2d* l, *r;
  Node2d() : l(nullptr), r(nullptr) {}
};
Node2d* root = new Node2d();
ll query(int s, int e, Node2d* curr, int l, int r, int sy, int ey) {
  if (l > r || curr == nullptr) return 0;
  if (s == l && e == r) return curr->t.query(1, input::C, curr->t.root, sy, ey);
  ll le = query(s, m, curr->l, l, min(m,r), sy, ey);
  ll ri = query(1+m, e, curr->r, max(1+m,l), r, sy, ey);
  return gcd(le,ri);
}
void update(int s, int e, Node2d* curr, int l, int r, int sy, int ey, ll add) {
  if (l > r) return;
  if (s == l && e == r) {
    curr->t.update(1, input::C, curr->t.root, sy, ey, add);
  } else {
    if (curr->l == nullptr) curr->l = new Node2d();
    if (curr->r == nullptr) curr->r = new Node2d();

    update(s, m, curr->l, l, min(m,r), sy, ey, add);
    update(1+m, e, curr->r, max(1+m,l), r, sy, ey, add);
    ll newval = gcd(curr->l->t.query(1, input::C, curr->l->t.root, sy, ey),
           curr->r->t.query(1, input::C, curr->r->t.root, sy, ey));
    curr->t.update(1, input::C, curr->t.root, sy, sy, newval);
  }
}}

void init(int R, int C) {
  input::R = R;
  input::C = C;
}

void update(int P, int Q, long long K) {
  ++P; ++Q;
  stree2d::update(1, input::R, stree2d::root, P, P, Q, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
  ++P; ++Q; ++U; ++V;
  return stree2d::query(1, input::R, stree2d::root, P, U, Q, V);
}

컴파일 시 표준 에러 (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