| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 97821 |
2019-02-18T16:35:50 Z |
tincamatei |
Game (IOI13_game) |
C++14 |
|
3 ms |
384 KB |
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int BIGBUCK = 785;
const int LILBUCK = 28;
const int MAX_N = 22000;
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;
}
int R, C;
struct Cell {
int r, c;
long long val;
bool operator< (const Cell &a) const {
return r < a.r || (r == a.r && c < a.c);
}
};
bool cmp(Cell a, Cell b) {
return a.c < b.c;
}
struct Bucket {
int x1, x2;
int sizebuck, nrb;
Cell cell[BIGBUCK];
int y1[BIGBUCK / LILBUCK + 1], y2[BIGBUCK / LILBUCK + 1];
long long buckRez[BIGBUCK / LILBUCK + 1];
void init() {
x1 = x2 = 0;
sizebuck = nrb = 0;
for(int i = 0; i < BIGBUCK; ++i)
cell[i] = {0, 0, 0};
for(int i = 0; i < BIGBUCK / LILBUCK + 1; ++i)
y1[i] = y2[i] = buckRez[i] = 0;
}
void pushCell(Cell x) {
cell[sizebuck++] = x;
}
void build() {
x1 = 1000000001;
x2 = -1;
nrb = 0;
std::sort(cell, cell + sizebuck, cmp);
for(int i = 0; i < sizebuck; ++i) {
if(i % LILBUCK == 0) {
buckRez[nrb] = 0;
y1[nrb] = cell[i].c;
++nrb;
}
x1 = min(x1, cell[i].r);
x2 = max(x2, cell[i].r);
buckRez[nrb - 1] = gcd2(buckRez[nrb - 1], cell[i].val);
y2[nrb - 1] = cell[i].c;
}
}
long long stankyleg(int yl, int yr) {
long long rez = 0LL;
for(int i = 0; i < nrb; ++i)
if(yl <= y1[i] && y2[i] <= yr)
rez = gcd2(rez, buckRez[i]);
else if(!(yr < y1[i] || y2[i] < yl)) {
for(int j = i * LILBUCK; j < (i + 1) * LILBUCK; ++j)
if(yl <= cell[j].c && cell[j].c <= yr)
rez = gcd2(rez, cell[j].val);
}
return rez;
}
void debug() {
printf("number of cells in bucket: %d; number of bucklets: %d\n", sizebuck, nrb);
printf("Row bounds %d %d\n", x1, x2);
for(int i = 0; i < sizebuck; ++i)
printf("Cell %d-> %d %d %lld\n", i, cell[i].r, cell[i].c, cell[i].val);
for(int j = 0; j < nrb; ++j) {
printf("Bucklet %d; bounds: %d %d; gcd: %lld\n", j, y1[j], y2[j], buckRez[j]);
}
}
};
map<pair<int, int>, long long> cellMap;
map<pair<int, int>, int> buckid;
set<Cell> cells;
struct ThisIsEpic {
int nrcells, nrb;
Cell cell[MAX_N];
Bucket dothe[MAX_N / BIGBUCK + 1];
Cell extra[BIGBUCK];
int nex;
void init() {
nex = 0;
nrcells = nrb = 0;
}
void lazyAdd(Cell x) {
cell[nrcells++] = x;
buckid[make_pair(x.r, x.r)] = -1;
if(nex == BIGBUCK)
this->build();
else
extra[nex++] = x;
}
void pushCell(Cell x) {
if(nrcells % BIGBUCK == 0) {
dothe[nrb].init();
dothe[nrb].x1 = x.r;
nrb++;
}
buckid[make_pair(x.r, x.c)] = nrb - 1;
dothe[nrb - 1].x2 = x.r;
dothe[nrb - 1].pushCell(x);
cell[nrcells++] = x;
}
void replaceCell(Cell x){
if(buckid[make_pair(x.r, x.c)] == -1)
for(int i = 0; i < nex; ++i)
if(extra[i].r == x.r && extra[i].c == x.c)
extra[i].val = x.val;
else {
int b = buckid[make_pair(x.r, x.c)];
for(int i = 0; i < dothe[b].sizebuck; ++i)
if(dothe[b].cell[i].r == x.r && dothe[b].cell[i].c == x.c)
dothe[b].cell[i].val = x.val;
dothe[b].build();
}
}
void build() {
this->init();
int i = 0;
for(auto it: cells)
pushCell(it);
for(int i = 0; i < nrb; ++i)
dothe[i].build();
}
long long BenShapiro(int xl, int xr, int yl, int yr) {
long long rez = 0LL;
for(int i = 0; i < nrb; ++i)
if(xl <= dothe[i].x1 && dothe[i].x2 <= xr)
rez = gcd2(rez, dothe[i].stankyleg(yl, yr));
else if(!(xr < dothe[i].x1 || dothe[i].x2 < xl)) {
for(int j = 0; j < dothe[i].sizebuck; ++j)
if(xl <= dothe[i].cell[j].r && dothe[i].cell[j].r <= xr &&
yl <= dothe[i].cell[j].c && dothe[i].cell[j].c <= yr)
rez = gcd2(rez, dothe[i].cell[j].val);
}
for(int i = 0; i < nex; ++i)
if(xl <= extra[i].r && extra[i].r <= xr &&
yl <= extra[i].c && extra[i].c <= yr)
rez = gcd2(rez, extra[i].val);
return rez;
}
void debug() {
printf("Number of cells: %d\nNumber of buckets: %d\n", nrcells, nrb);
for(int i = 0; i < nrb; ++i) {
printf("BUCKET %d\n", i);
dothe[i].debug();
}
printf("------------------------------------------------------------------\n");
}
} xdxd;
void init(int _R, int _C) {
R = _R;
C = _C;
}
void update(int P, int Q, long long K) {
//printf("UPDATE: %d %d %lld\n", P, Q, K);
if(cellMap[make_pair(P, Q)] != 0) {
cells.erase({P, Q, cellMap[make_pair(P, Q)] - 1});
cells.insert({P, Q, K});
xdxd.replaceCell({P, Q, K});
} else {
cells.insert({P, Q, K});
xdxd.lazyAdd({P, Q, K});
}
cellMap[make_pair(P, Q)] = K + 1;
//printf("CELLS!!!!!!\n");
//for(auto it: cells)
// printf("%d %d %d\n", it.r, it.c, it.val);
//printf("/CELLS\n");
//xdxd.debug();
}
long long calculate(int P, int Q, int U, int V) {
return xdxd.BenShapiro(P, U, Q, V);
}
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;
^~~
game.cpp: In member function 'void ThisIsEpic::replaceCell(Cell)':
game.cpp:137:11: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
if(buckid[make_pair(x.r, x.c)] == -1)
^
game.cpp: In member function 'void ThisIsEpic::build()':
game.cpp:153:7: warning: unused variable 'i' [-Wunused-variable]
int i = 0;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
256 KB |
Output is correct |
| 2 |
Correct |
3 ms |
384 KB |
Output is correct |
| 3 |
Correct |
3 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
3 ms |
384 KB |
Output is correct |
| 3 |
Correct |
3 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
3 ms |
384 KB |
Output is correct |
| 3 |
Correct |
3 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
