Submission #561496

#TimeUsernameProblemLanguageResultExecution timeMemory
561496peuchJousting tournament (IOI12_tournament)C++17
100 / 100
267 ms32644 KiB
#include<bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> const int MAXN = 1e5 + 10; int bit1[MAXN], bit2[MAXN]; int n, c, r; vector<int> ini, fim; void upd1(int id, int val); int qry1(int id); void upd2(int id, int val); int qry2(int id); vector<int> seg, e, d; vector<int> bank; struct event{ int l, r, id; event(int _l, int _r, int _id){ l = _l; r = _r; id = _id; } bool operator < (event x) const{ if(r != x.r) return r < x.r; return id < x.id; } }; vector<event> line; int copia(int node); int update(int pos, int ini, int fim, int id, int val); int query(int pos, int ini, int fim, int p, int q); int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) { copia(-1); copia(-1); n = N, c = C, r = R; ini = fim = bank = vector<int> (n); // Reindex fights ordered_set fila1, fila2; for(int i = 0; i < n; i++) fila1.insert(i), fila2.insert(i); for(int i = 0; i < c; i++){ int auxA = S[i], auxB = E[i]; S[i] = *fila1.find_by_order(S[i]); E[i] = *fila2.find_by_order(E[i]); for(int j = auxB; j > auxA; j--) fila1.erase(fila1.find_by_order(j)); for(int j = auxB - 1; j >= auxA; j--) fila2.erase(fila2.find_by_order(j)); } // Create intervals when fighter start at i for(int val = 0, i = 0; i < n; i++){ ini[i] = val; if(i != n - 1 && K[i] > r) val = i + 1; } for(int val = n - 1, i = n - 1; i >= 0; i--){ if(i != n - 1 && K[i] > r) val = i; fim[i] = val; } // Create LineSweep events for(int i = 0; i < c; i++) line.push_back(event(S[i], E[i], -1)); for(int i = 0; i < n; i++) line.push_back(event(ini[i], fim[i], i)); sort(line.begin(), line.end()); // Answer linesweep queries bank[0] = 1; int ans = -1, idx = 0, last = 0; for(int i = 0; i < line.size(); i++){ int esq = line[i].l; int dir = line[i].r; int id = line[i].id; // printf("Event: %d %d %d\n", esq, dir, id); while(last != dir){ last++; bank[last] = bank[last - 1]; } if(id == -1) bank[dir] = update(bank[dir], 0, n - 1, esq, 1); else{ int auxAns = query(bank[dir], 0, n - 1, esq, id); if(id != 0) auxAns -= query(bank[id - 1], 0, n - 1, esq, id); // printf("Ans = %d at %d (%d %d %d)\n", auxAns, id, esq, id, dir); if(auxAns > ans) idx = id, ans = auxAns; if(ans == auxAns) idx = min(id, idx); } // printf("%d\n", bank[dir]); // for(int i = 0; i < n; i++) // printf("%d ", query(bank[dir], 0, n - 1, i, i)); // printf("\n"); } // printf("%d\n", ans); return idx; } void upd1(int id, int val){ id++; while(id < MAXN){ bit1[id] += val; id += (-id)&id; } } int qry1(int id){ id++; int ret = 0; while(id > 0){ ret += bit1[id]; id -= (-id)&id; } return ret; } void upd2(int id, int val){ id++; while(id < MAXN){ bit2[id] += val; id += (-id)&id; } } int qry2(int id){ id++; int ret = 0; while(id > 0){ ret += bit2[id]; id -= (-id)&id; } return ret; } int copia(int node){ if(node == -1){ seg.push_back(0); e.push_back(0); d.push_back(0); } else{ seg.push_back(seg[node]); e.push_back(e[node]); d.push_back(d[node]); } return seg.size() - 1; } int update(int pos, int ini, int fim, int id, int val){ if(ini > id || fim < id) return pos; int newNode = copia(pos); // printf("Updating: (%d -> %d) %d %d %d %d\n", pos, newNode, ini, fim, id, val); if(ini == fim){ seg[newNode] += val; return newNode; } int mid = (ini + fim) >> 1; int aux; aux = update(e[pos], ini, mid, id, val); e[newNode] = aux; // printf("(%d %d %d %d %d) Returned %d\n", e[pos], ini, mid, id, val, e[newNode]); aux = update(d[pos], mid + 1, fim, id, val); d[newNode] = aux; // printf("(%d %d %d %d %d) Returned %d\n", d[pos], mid + 1, fim, id, val, d[newNode]); seg[newNode] = seg[e[newNode]] + seg[d[newNode]]; // printf("seg[%d -> (%d %d)] = %d\n", newNode, e[newNode], d[newNode], seg[newNode]); return newNode; } int query(int pos, int ini, int fim, int p, int q){ if(pos <= 0) return 0; if(ini > q || fim < p) return 0; if(ini >= p && fim <= q) return seg[pos]; int mid = (ini + fim) >> 1; return query(e[pos], ini, mid, p, q) + query(d[pos], mid + 1, fim, p, q); }

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:84:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |  for(int i = 0; i < line.size(); i++){
      |                 ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...