| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 402808 |
2021-05-12T11:26:05 Z |
prvocislo |
Game (IOI13_game) |
C++17 |
|
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++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
