Submission #97810

#TimeUsernameProblemLanguageResultExecution timeMemory
97810tincamateiGame (IOI13_game)C++14
37 / 100
13099 ms9420 KiB
#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 replaceCell(Cell x) { for(int i = 0; i < sizebuck; ++i) if(cell[i].r == x.r && cell[i].c == x.c) cell[i].val = x.val; this->build(); } void build() { 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; } 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; 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; if(nex == BIGBUCK) this->build(); } void pushCell(Cell x) { if(nrcells % BIGBUCK == 0) { dothe[nrb].init(); dothe[nrb].x1 = x.r; nrb++; } dothe[nrb - 1].x2 = x.r; dothe[nrb - 1].pushCell(x); cell[nrcells++] = x; } 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.build(); } else { cells.insert({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.build(); //xdxd.debug(); } long long calculate(int P, int Q, int U, int V) { return xdxd.BenShapiro(P, U, Q, V); }

Compilation message (stderr)

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::build()':
game.cpp:134:7: warning: unused variable 'i' [-Wunused-variable]
   int i = 0;
       ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...