| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 572754 | kartel | 카니발 티켓 (IOI20_tickets) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
//#include "grader.cpp"
#include "tickets.h"
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define F first
#define S second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef tree<pair <int, int> , null_type, less<pair <int, int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
long long find_maximum(int k, vector <vector <int> > x) {
int n = sz(x);
vector <vector <int> > ans(n, vector <int> (m, -1));
vector <int> le(n, 0);
vector <int> ri(n, m - 1);
ll sum = 0;
for (int it = 0; it < k; it++) {
vector <pair <int, pair <int, int> > > vl;
ll curL = 0, curR = 0;
ll mx = -1, mI = 0, mJ = 0;
ordered_set se;
for (int i = 0; i < n; i++) {
while (le[i] < m && ans[i][le[i]] != -1) {
le[i]++;
}
while (ri[i] >= 0 && ans[i][ri[i]] != -1) {
ri[i]--;
}
vl.pb({x[i][le[i]], {x[i][ri[i]] - x[i][le[i]], i}});
curR += x[i][ri[i]];
}
auto add = [&](int val, int i) {
if (sz(se) < n / 2 - 1) {
se.insert({val, i});
curL += x[i][le[i]];
return;
}
if (se.order_of_key(make_pair(val, 0)) < n / 2 - 1) {
auto it = *se.find_by_order(n / 2 - 2);
curR += x[it.F][ri[it.F]]; curL -= x[it.F][le[it.F]];
curL += x[i][le[i]];
} else {
curR += x[i][ri[i]];
}
se.insert({val, i});
};
auto del = [&](int val, int i) {
if (sz(se) <= n / 2 - 1) {
assert(se.find(make_pair(val, i)) != se.end());
se.erase(se.find({val, i}));
curL -= x[i][le[i]];
return;
}
se.erase(se.find({val, i}));
if (se.order_of_key(make_pair(val, 0)) < n / 2 - 1) {
auto it = *se.find_by_order(n / 2 - 2);
curR -= x[it.F][ri[it.F]]; curL += x[it.F][le[it.F]];
curL -= x[i][le[i]];
} else {
curR -= x[i][ri[i]];
}
};
sort(all(vl));
vector <pair <int, pair <int, int> > > a;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (ans[i][j] == -1) {
a.pb({x[i][j], {i, j}});
}
}
}
sort(all(a));
int j = 0;
for (int i = 0; i < sz(a); i++) {
int val = a[i].F, I = a[i].S.F, J = a[i].S.S;
while (j < sz(vl) && vl[j].F <= val) {
curR -= x[vl[j].S.S][ri[vl[j].S.S]];
add(vl[j].S.F, vl[j].S.S);
j++;
}
del(x[I][ri[I]] - x[I][le[I]], I);
if (sz(se) >= n / 2 - 1 && mx < val * 1ll * (n / 2 - 1) - curL + curR - val * 1ll * (n - n / 2)) {
mx = val * 1ll * (n / 2 - 1) - curL + curR - val * 1ll * (n - n / 2);
mI = I; mJ = J;
}
add(x[I][ri[I]] - x[I][le[I]], I);
}
assert(mx != -1);
set <pair <int, int> > sse;
for (int i = 0; i < n; i++) {
if (mI == i) {
continue;
}
if (x[i][le[i]] < x[mI][mJ]) {
sse.insert({x[i][ri[i]] - x[i][le[i]], i});
} else {
sse.insert({2e9, i});
}
}
int tmp = 0;
for (auto [val, i] : sse) {
if (tmp == n / 2 - 1) {
ans[i][ri[i]] = it;
continue;
}
tmp++;
ans[i][le[i]] = it;
}
ans[mI][mJ] = it;
sum += mx;
}
allocate_tickets(ans);
return sum;
}