제출 #261719

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
261719		smax	게임 (IOI13_game)	C++17	37 / 100	2337 ms	256004 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;

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

struct Node {
    long long ans;
    int l, r;
    Node *left, *right;

    Node() {}

    Node(int _l, int _r) : ans(0), l(_l), r(_r), left(NULL), right(NULL) {}

    void extend() {
        if (!left) {
            int m = (l + r) / 2;
            left = new Node(l, m);
            right = new Node(m+1, r);
        }
    }
};

long long query(Node *p, int i, int j) {
    if (i > p->r || j < p->l)
        return 0;
    if (i <= p->l && p->r <= j)
        return p->ans;

    p->extend();
    return gcd2(query(p->left, i, j), query(p->right, i, j));
}

void update(Node *p, int idx, long long val) {
    if (p->l == p->r) {
        p->ans = val;
        return;
    }

    p->extend();
    int m = (p->l + p->r) / 2;
    if (idx <= m)
        update(p->left, idx, val);
    else
        update(p->right, idx, val);
    p->ans = gcd2(p->left->ans, p->right->ans);
}

void update_y(Node *cur, Node *curL, Node *curR, int y, long long val) {
    if (cur->l == cur->r) {
        cur->ans = gcd2(curL->ans, curR->ans);
        return;
    }

    cur->extend();
    curL->extend();
    curR->extend();
    int m = (cur->l + cur->r) / 2;
    if (y <= m)
        update_y(cur->left, curL->left, curR->left, y, val);
    else
        update_y(cur->right, curL->right, curR->right, y, val);
    cur->ans = gcd2(cur->left->ans, cur->right->ans);
}

struct Seg {
    int n, l, r;
    Node yNode;
    Seg *left, *right;

    Seg() {}

    Seg(int _n, int _l, int _r) : n(_n), l(_l), r(_r), yNode(0, n-1), left(NULL), right(NULL) {}

    void extend() {
        if (!left) {
            int m = (l + r) / 2;
            left = new Seg(n, l, m);
            right = new Seg(n, m+1, r);
        }
    }
} st;

long long query(Seg *p, int ix, int iy, int jx, int jy) {
    if (ix > p->r || jx < p->l)
        return 0;
    if (ix <= p->l && p->r <= jx)
        return query(&p->yNode, iy, jy);

    p->extend();
    return gcd2(query(p->left, ix, iy, jx, jy), query(p->right, ix, iy, jx, jy));
}

void update(Seg *p, int x, int y, long long val) {
    if (p->l == p->r) {
        update(&p->yNode, y, val);
        return;
    }

    p->extend();
    int m = (p->l + p->r) / 2;
    if (x <= m)
        update(p->left, x, y, val);
    else
        update(p->right, x, y, val);
    update_y(&p->yNode, &p->left->yNode, &p->right->yNode, y, val);
}

void init(int R, int C) {
    st = Seg(C, 0, R - 1);
}

void update(int P, int Q, long long K) {
    update(&st, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return query(&st, P, Q, U, 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: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20