제출 #402808

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
402808		prvocislo	게임 (IOI13_game)	C++17	10 / 100	1378 ms	11132 KiB

game

#include "game.h"
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
typedef long long ll;
using namespace std;

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;
}
const int K = 50;
int r, c, last = 0;
vector<vector<ll> > st; 
vector<vector<int> > val;
vector<int> x;
struct upd { int x, y; ll k; };
void init(int R, int C) { r = R, c = C; }
ll query_1d(int li, int ri, int vr) {
    ll g = 0;
    li = lower_bound(val[vr].begin(), val[vr].end(), li) - val[vr].begin();
    ri = upper_bound(val[vr].begin(), val[vr].end(), ri) - val[vr].begin();
    for (li += val[vr].size(), ri += val[vr].size(); li < ri; li >>= 1, ri >>= 1) {
        if (li & 1) g = gcd(g, st[vr][li++]);
        if (ri & 1) g = gcd(g, st[vr][--ri]);
    } return g;
}
vector<upd> u;
map<pair<int, int>, ll> m;
ll query_2d(int lx, int ly, int rx, int ry) {
    lx = lower_bound(x.begin(), x.end(), lx) - x.begin();
    rx = upper_bound(x.begin(), x.end(), rx) - x.begin();
    ll g = 0;
    for (lx += x.size(), rx += x.size(); lx < rx; lx >>= 1, rx >>= 1) {
        if (lx & 1) g = gcd(g, query_1d(ly, ry, lx++));
        if (rx & 1) g = gcd(g, query_1d(ly, ry, --rx));
    }
    return g;
}
long long calculate(int lx, int ly, int rx, int ry) {
    ll g = query_2d(lx, ly, rx, ry);
    for (int i = last; i < u.size(); i++)
        if (lx <= u[i].x && u[i].x <= rx && ly <= u[i].y && u[i].y <= ry)
            g = gcd(g, u[i].k);
    return g;
}
void merge(int v)
{
    vector<ll> lf;
    int lv = (v << 1), rv = ((v << 1) | 1), li = 0, ri = 0;
    while (li < val[lv].size() || ri < val[rv].size()) {
        int i, j;
        if (ri == val[rv].size() || (li < val[lv].size() && val[lv][li] < val[rv][ri])) i = lv, j = li++;
        else i = rv, j = ri++;
        if (val[v].empty() || val[v].back() < val[i][j]) val[v].push_back(val[i][j]), lf.push_back(0);
        lf.back() = gcd(lf.back(), st[i][val[i].size() + j]);
    }
    st[v].assign(lf.size() * 2, 0);
    for (int i = 0; i < lf.size(); i++) st[v][i + lf.size()] = lf[i];
}
void update(int X, int Y, ll k) {
    u.push_back({ X, Y, k });
    if (m.count({ X, Y })) u[m[{X, Y}]].x = -1;
    m[{X, Y}] = u.size() - 1;
    if (last + K > u.size()) return;
    x.clear();
    for (int i = 0; i < u.size(); i++) if (u[i].x > -1) x.push_back(u[i].x);
    sort(x.begin(), x.end()), x.erase(unique(x.begin(), x.end()), x.end());
    int n = x.size();
    val.assign(2 * n, vector<int>()), st.assign(n * 2, vector<ll>());
    for (int i =0; i < u.size(); i++) {
        if (u[i].x == -1) continue;
        int ix = lower_bound(x.begin(), x.end(), u[i].x) - x.begin();
        val[n + ix].push_back(u[i].y);
    }
    for (int i = n; i < 2 * n; i++) {
        sort(val[i].begin(), val[i].end());
        val[i].erase(unique(val[i].begin(), val[i].end()), val[i].end());
        st[i].assign(val[i].size() * 2, 0);
    }
    for (const upd& i : u) {
        if (i.x == -1) continue;
        int ix = lower_bound(x.begin(), x.end(), i.x) - x.begin();
        int iy = lower_bound(val[n + ix].begin(), val[n + ix].end(), i.y) - val[n + ix].begin();
        st[n + ix][val[n + ix].size() + iy] = i.k;
    }
    for (int i = n - 1; i > 0; i--)
        merge(i);
    for (int i = 0; i < 2 * n; i++)
        for (int j = val[i].size() - 1; j > 0; j--) st[i][j] = gcd(st[i][j << 1], st[i][(j << 1) | 1]);
    last = u.size();
}

컴파일 시 표준 에러 (stderr) 메시지

game.cpp: In function 'long long int calculate(int, int, int, int)':
game.cpp:46:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<upd>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int i = last; i < u.size(); i++)
      |                        ~~^~~~~~~~~~
game.cpp: In function 'void merge(int)':
game.cpp:55:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     while (li < val[lv].size() || ri < val[rv].size()) {
      |            ~~~^~~~~~~~~~~~~~~~
game.cpp:55:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     while (li < val[lv].size() || ri < val[rv].size()) {
      |                                   ~~~^~~~~~~~~~~~~~~~
game.cpp:57:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         if (ri == val[rv].size() || (li < val[lv].size() && val[lv][li] < val[rv][ri])) i = lv, j = li++;
      |             ~~~^~~~~~~~~~~~~~~~~
game.cpp:57:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         if (ri == val[rv].size() || (li < val[lv].size() && val[lv][li] < val[rv][ri])) i = lv, j = li++;
      |                                      ~~~^~~~~~~~~~~~~~~~
game.cpp:63:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for (int i = 0; i < lf.size(); i++) st[v][i + lf.size()] = lf[i];
      |                     ~~^~~~~~~~~~~
game.cpp: In function 'void update(int, int, ll)':
game.cpp:69:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<upd>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     if (last + K > u.size()) return;
      |         ~~~~~~~~~^~~~~~~~~~
game.cpp:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<upd>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for (int i = 0; i < u.size(); i++) if (u[i].x > -1) x.push_back(u[i].x);
      |                     ~~^~~~~~~~~~
game.cpp:75:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<upd>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for (int i =0; i < u.size(); i++) {
      |                    ~~^~~~~~~~~~

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