oj.uz

답안 #402808

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
402808 2021-05-12T11:26:05 Z prvocislo 게임 (IOI13_game) C++17
10 / 100
 1378 ms 11132 KB 
#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();
}

Compilation message

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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 288 KB Output is correct
6 Correct 1 ms 288 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 789 ms 9736 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 292 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1155 ms 11132 KB Output is correct
13 Incorrect 1378 ms 4360 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Incorrect 720 ms 9732 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Incorrect 697 ms 9768 KB Output isn't correct
13 Halted 0 ms 0 KB -