oj.uz

답안 #261011

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
261011 2020-08-11T09:52:29 Z SamAnd 게임 (IOI13_game) C++17
0 / 100
 1 ms 384 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const int T = 22003 * 30 * 30;

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

int R, C;

map<int, map<int, int> > g;

void ubdy(int tlx, int trx, int tly, int try_, int x, int y, ll k, int posx, int posy)
{
    if (tly == try_)
    {
        if (tlx == trx)
        {
            g[posx][posy] = k;
            return;
        }
        g[posx][posy] = gcd(g[posx * 2][posy], g[posx * 2 + 1][posy]);
        return;
    }
    int m = (tly + try_) / 2;
    if (y <= m)
        ubdy(tlx, trx, tly, m, x, y, k, posx, posy * 2);
    else
        ubdy(tlx, trx, m + 1, try_, x, y, k, posx, posy * 2 + 1);
    g[posx][posy] = gcd(g[posx][posy * 2], g[posx][posy * 2 + 1]);
}

void ubdx(int tlx, int trx, int x, int y, ll k, int posx)
{
    if (tlx == trx)
    {
        ubdy(tlx, trx, 0, C - 1, x, y, k, posx, 1);
        return;
    }
    int m = (tlx + trx) / 2;
    if (x <= m)
        ubdx(tlx, m, x, y, k, posx * 2);
    else
        ubdx(m + 1, trx, x, y, k, posx * 2 + 1);
    ubdy(tlx, trx, 0, C - 1, x, y, k, posx, 1);
}

ll qryy(int tly, int try_, int ly, int ry, int posx, int posy)
{
    if (ly > ry)
        return 0;
    if (g.find(posx) == g.end())
        return 0;
    if (g[posx].find(posy) == g[posx].end())
        return 0;
    if (tly == ly && try_ == ry)
        return g[posx][posy];
    int m = (tly + try_) / 2;
    return gcd(qryy(tly, m, ly, min(m, ry), posx, posy * 2),
               qryy(m + 1, try_, max(m + 1, ly), ry, posx, posy * 2 + 1));
}

ll qryx(int tlx, int trx, int lx, int rx, int ly, int ry, int posx)
{
    if (lx > rx)
        return 0;
    if (tlx == lx && trx == rx)
    {
        return qryy(0, C - 1, ly, ry, posx, 1);
    }
    int m = (tlx + trx) / 2;
    return gcd(qryx(tlx, m, lx, min(m, rx), ly, ry, posx * 2),
               qryx(m + 1, trx, max(m + 1, lx), rx, ly, ry, posx * 2 + 1));
}

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

void update(int P, int Q, long long K)
{
    ubdx(0, R - 1, P, Q, K, 1);
}

long long calculate(int P, int Q, int U, int V)
{
    return qryx(0, R - 1, P, U, Q, V, 1);
}

Compilation message

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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -