이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int bit[MAXN];
int n, c, r;
vector<int> ini, fim;
void upd(int id, int val);
int qry(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
for(int i = 0; i < c; i++){
int aux = E[i] - S[i];
S[i] += qry(S[i] - 1);
E[i] += qry(E[i]);
upd(S[i], aux);
}
// 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());
memset(bit, 0, sizeof(bit));
// 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 upd(int id, int val){
id++;
while(id < MAXN){
bit[id] += val;
id += (-id)&id;
}
}
int qry(int id){
id++;
int ret = 0;
while(id > 0){
ret += bit[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);
}
컴파일 시 표준 에러 (stderr) 메시지
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:72:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(int i = 0; i < line.size(); i++){
| ~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |