이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin ("idk.in");
ofstream cout ("idk.out");
const int N = 2e5 + 5;
int n, m;
struct idk {
long long v, c;
} v[N];
bool cmp(idk x, idk y) {
return x.c < y.c;
}
namespace segment_tree {
struct nod {
vector <long long> val, sp;
} a[4 * N];
vector <int> noduri;
int start;
void build() {
for (int i = start - 1; i; --i) {
int sz = a[i + i].val.size();
int p1 = 0, p2 = 0;
while((p1 < sz || p2 < sz) && p1 + p2 < m) {
if (p2 == sz || p1 < sz && a[i + i].val[p1] > a[i + i + 1].val[p2]) {
a[i].val.push_back(a[i + i].val[p1]);
++p1;
} else {
a[i].val.push_back(a[i + i + 1].val[p2]);
++p2;
}
}
long long sum = 0;
for (auto it : a[i].val) {
sum += it;
a[i].sp.push_back(sum);
}
}
}
long long nr_bigger(int nod, long long val) {
int st = 0, dr = a[nod].val.size() - 1, mij, ans = 0;
while (st <= dr) {
mij = (st + dr) / 2;
if (a[nod].val[mij] >= val) {
ans = mij + 1;
st = mij + 1;
}
else dr = mij - 1;
}
return ans;
}
long long sum_bigger(int nod, long long val) {
int st = 0, dr = a[nod].val.size() - 1, mij, ans = 0;
while (st <= dr) {
mij = (st + dr) / 2;
if (a[nod].val[mij] >= val) {
ans = mij + 1;
st = mij + 1;
}
else dr = mij - 1;
}
if (ans == 0)
return 0;
return a[nod].sp[ans - 1];
}
int nr_noduri(int val) {
int ans = 0;
for (auto it : noduri) {
ans += nr_bigger(it, val);
}
return ans;
}
long long sum_noduri(long long val) {
long long ans = 0;
for (auto it : noduri) {
ans += sum_bigger(it, val);
}
long long aux = nr_noduri(val);
return ans - (aux - (long long)m) * val;
}
void Query_aint(int st, int dr) {
if (st & 1)
noduri.push_back(st++);
if (!(dr & 1))
noduri.push_back(dr--);
if (st <= dr)
Query_aint(st / 2, dr / 2);
}
long long Query(int st, int dr) {
st += start - 1, dr += start - 1;
noduri.clear();
Query_aint(st, dr);
for (auto it : noduri) {
int st = 0, dr = a[it].val.size() - 1, mij;
while (st <= dr) {
mij = (st + dr) / 2;
long long aux = nr_noduri(a[it].val[mij]);
if (aux < m) {
st = mij + 1;
continue;
}
if (nr_noduri(a[it].val[mij] + 1) < m) {
return sum_noduri(a[it].val[mij]);
}
dr = mij - 1;
}
}
}
void init() {
start = 1;
while (start < n) {
start <<= 1;
}
for (int i = 1; i <= n; ++i) {
a[i + start - 1].val.push_back(v[i].v);
a[i + start - 1].sp.push_back(v[i].v);
}
for (int i = n + 1; i <= start; ++i) {
a[i + start - 1].val.push_back(0);
a[i + start - 1].sp.push_back(0);
}
build();
}
}
int calc(int x, int r) {
if (r - x + 1 < m || r > n || r < 1 || x > n || x < 1)
return -1;
return segment_tree::Query(x, r) - 2 * (v[r].c - v[x].c);
}
int ans[N];
long long Max[N];
bool viz[N];
void find_ans(int poz, int st, int dr, int l, int r) {
if (ans[poz] || l > r || poz < l || r < poz || st == 0 && dr == 0 || viz[poz])
return;
viz[poz] = true;
for (int i = max(st, poz + m - 1); i <= dr; ++i) {
long long k = calc(poz, i);
if (k >= Max[poz]) {
Max[poz] = k;
ans[poz] = i;
}
}
if (poz != l)
find_ans((l + poz) / 2, st, ans[poz], l, poz - 1);
if (poz != r)
find_ans((r + poz) / 2, ans[poz], dr, poz + 1, r);
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> v[i].v >> v[i].c;
}
sort (v + 1, v + n + 1, cmp);
segment_tree::init();
find_ans((n + 1) / 2, (n + 1) / 2, n, 1, n);
long long ANS = 0;
for (int i = 1; i <= n; ++i) {
ANS = max(ANS, Max[i]);
}
cout << ANS;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
cake3.cpp: In function 'void segment_tree::build()':
cake3.cpp:36:41: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
36 | if (p2 == sz || p1 < sz && a[i + i].val[p1] > a[i + i + 1].val[p2]) {
cake3.cpp: In function 'void find_ans(int, int, int, int, int)':
cake3.cpp:156:60: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
156 | if (ans[poz] || l > r || poz < l || r < poz || st == 0 && dr == 0 || viz[poz])
| ~~~~~~~~^~~~~~~~~~
cake3.cpp: In function 'long long int segment_tree::Query(int, int)':
cake3.cpp:125:5: warning: control reaches end of non-void function [-Wreturn-type]
125 | }
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |