제출 #98124

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
98124		MiricaMatei	게임 (IOI13_game)	C++14	63 / 100	12195 ms	32732 KiB

game

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

using namespace std;

int N, M;

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

long long coord(int x, int y) {
  return 1LL * (y - 1) * N + x;
}

struct Treap {
  Treap* left;
  Treap* right;
  int sz, prio;
  long long pos, val, gcd;
};

Treap* emptyTreap = new Treap {NULL, NULL, 0, 0, 0LL, 0LL, 0LL};

void recompute(Treap* root) {
  if (root != emptyTreap) {
    root->sz = root->left->sz + 1 + root->right->sz;
    root->gcd = gcd2(gcd2(root->left->gcd, root->right->gcd), root->val);
  }
}

pair<Treap*, Treap*> split(Treap* root, int pos) {
  if (root == emptyTreap)
    return {emptyTreap, emptyTreap};
  pair<Treap*, Treap*> ans;
  if (root->pos <= pos) {
    ans.first = root;
    pair<Treap*, Treap*>aux = split(root->right, pos);
    ans.second = aux.second;
    ans.first->right = aux.first;
  } else {
    ans.second = root;
    pair<Treap*, Treap*>aux = split(root->left, pos);
    ans.first = aux.first;
    ans.second->left = aux.second;
  }
  recompute(ans.first);
  recompute(ans.second);
  return ans;
}

Treap* join(Treap* a, Treap* b) {
  if (a == emptyTreap)
    return b;
  if (b == emptyTreap)
    return a;
  if (a->prio < b->prio) {
    a->right = join(a->right, b);
    recompute(a);
    return a;
  } else {
    b->left = join(a, b->left);
    recompute(b);
    return b;
  }
}

Treap* TreapUpdate(Treap* root, long long pos, long long val) {
  pair<Treap*, Treap*>aux1 = split(root, pos - 1);
  pair<Treap*, Treap*>aux2 = split(aux1.second, pos);
  Treap* newTreap = new Treap {emptyTreap, emptyTreap, 1, rand(), pos, val, val};
  Treap* view = join(join(aux1.first, newTreap), aux2.second);
  return view;
}

long long TreapQuery(Treap* root, long long pos1, long long pos2) {
  pair<Treap*, Treap*>aux1 = split(root, pos1 - 1);
  pair<Treap*, Treap*>aux2 = split(aux1.second, pos2);
  long long answer = 0;
  if (aux2.first != emptyTreap)
    answer = aux2.first->gcd;
  root = join(join(aux1.first, aux2.first), aux2.second);
  return answer;
}

struct SegTree {
  Treap* treap;
  SegTree* left;
  SegTree* right;
};

SegTree* emptyTree = new SegTree {emptyTreap, NULL, NULL};
SegTree* Root;


SegTree* SegTreeUpdate(SegTree* root, int l, int r, int P, int Q, long long K) {
  if (root == emptyTree)
    root = new SegTree {emptyTreap, emptyTree, emptyTree};
  root->treap = TreapUpdate(root->treap, coord(P, Q), K);
  if (l == r)
    return root;
  int mid = (l + r) / 2;
  if (P <= mid)
    root->left = SegTreeUpdate(root->left, l, mid, P, Q, K);
  else
    root->right = SegTreeUpdate(root->right, mid + 1, r, P, Q, K);
  return root;
}

long long SegTreeQuery(SegTree* root, int l, int r, int P, int Q, int U, int V) {
  if (root == emptyTree)
    return 0;
  if (P <= l && r <= U)
    return TreapQuery(root->treap, coord(P, Q), coord(U, V));
  if (U < l)
    return 0;
  if (r < P)
    return 0;
  int mid = (l + r) / 2;
  return gcd2(SegTreeQuery(root->left, l, mid, P, Q, U, V), SegTreeQuery(root->right, mid + 1, r, P, Q, U, V));
}

void init(int R, int C) {
  srand(time(NULL));
  Root = emptyTree;
  N = R;
  M = C;
}

void update(int P, int Q, long long K) {
  Root = SegTreeUpdate(Root, 1, N, P + 1, Q + 1, K);
}

long long calculate(int P, int Q, int U, int V) {
  return SegTreeQuery(Root, 1, N, P + 1, Q + 1, U + 1, V + 1);
}

/*int main() {
  freopen("date.in", "r", stdin);
  freopen("date.out", "w", stdout);

  int R, C;
  scanf("%d%d", &R, &C);
  init(R, C);
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    int t;
    scanf("%d", &t);
    if (t == 1) {
      int P, Q;
      long long K;
      scanf("%d%d", &P, &Q);
      scanf("%lld", &K);
      update(P, Q, K);
    } else {
      int P, Q, U, V;
      scanf("%d%d%d%d", &P, &Q, &U, &V);
      printf("%lld\n", calculate(P, Q, U, V));
    }
  }

  return 0;
}
*/

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