이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "train.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const long long INF = 1'000'000'000'000'000;
const ll INF32 = 1'000'000'001;
void upd(ll w, vector<long long>& all, ll c, ll nw, vector<pair<ll, ll>>& eat) {
for (ll i = 0; i < (1 << w); i++) {
bool b = false;
for (ll j = 0; j < w; j++) {
if (!((i >> j) & 1)) {
if (eat[j].first <= nw) all[i + (1 << j)] = min(all[i] + c, all[i + (1 << j)]);
if (eat[j].second < nw) b = true;
}
}
if (b) all[i] = INF;
}
}
struct BIT {
vector<ll> tree;
vector<ll> all;
BIT(vector<ll> a) {
all = a;
all.push_back(-1);
all.push_back(INF32);
sort(all.begin(), all.end());
tree.resize(all.size() + 1);
}
ll s(ll x) {
return lower_bound(all.begin(), all.end(), x) - all.begin();
}
void add(ll x) {
x = s(x);
x++;
for (; x < tree.size(); x += x & -x) tree[x]++;
}
ll get(ll l, ll r) {
return get(r) - get(l);
}
ll get(ll x) {
x = s(x);
ll ans = 0;
for (; x > 0; x -= x & -x) ans += tree[x];
return ans;
}
};
long long solve(int N, int M, int W, vector<int> T, vector<int> X, vector<int> Y, vector<int> A, vector<int> B, vector<int> C, vector<int> L, vector<int> R) {
if (W <= 10 && N <= 1000 && M <= 1000) {
vector<pair<ll, ll>> eat;
multiset<tuple<ll, ll, ll, long long, ll>> s;
for (ll i = 0; i < W; i++) eat.emplace_back(L[i], R[i]);
sort(eat.begin(), eat.end());
vector<vector<long long>> ans(N, vector<long long>(1 << W, INF));
ans[0][0] = 0;
for (ll i = 0; i < M; i++) s.emplace(A[i], 2, i, 0ll, 0);
while (!s.empty()) {
auto[nt, t, i, c, m] = *s.begin();
s.erase(s.begin());
if (t == 2) {
upd(W, ans[X[i]], T[X[i]], nt, eat);
ll nc = 0;
for (ll j = 0; j < W; j++) if (eat[j].first <= B[i] && eat[j].second >= nt) nc += 1 << j;
for (ll j = 0; j < (1 << W); j++) s.emplace(B[i], 1, i, C[i] + ans[X[i]][j], j | nc);
} else ans[Y[i]][m] = min(ans[Y[i]][m], c);
}
upd(W, ans.back(), T.back(), INF32, eat);
if (ans.back().back() >= INF) return -1;
return ans.back().back();
}
vector<pair<ll, ll>> eat;
multiset<tuple<ll, ll, ll, long long>> s;
vector<ll> all;
for (ll i = 0; i < W; i++) {
eat.emplace_back(R[i], L[i]);
s.emplace(R[i], 3, i, 0ll);
s.emplace(L[i], 0, 0, 0ll);
all.push_back(L[i]);
}
BIT bi(all);
sort(eat.begin(), eat.end());
vector<deque<pair<long long, pair<long long, long long>>>> nmaco(N);
nmaco[0].emplace_back(0, make_pair(0, 0));
for (ll i = 0; i < M; i++) s.emplace(A[i], 2, i, 0ll);
long long co = 0, maco = 0;
while (!s.empty()) {
auto[_, t, i, c] = *s.begin();
s.erase(s.begin());
if (t == 0) {
maco++;
continue;
}
if (t == 3) {
bi.add(L[i]);
co++;
continue;
}
if (t == 2) {
if (nmaco[X[i]].empty()) continue;
while (nmaco[X[i]].size() > 1 && nmaco[X[i]][0].first + (nmaco[X[i]][0].second.first + bi.get(nmaco[X[i]][0].second.second, INF32)) * T[X[i]] >= nmaco[X[i]][1].first + (nmaco[X[i]][1].second.first + bi.get(nmaco[X[i]][1].second.second, INF32)) * T[X[i]]) nmaco[X[i]].pop_front();
s.emplace(B[i], 1, i, C[i] + nmaco[X[i]].front().first + (nmaco[X[i]].front().second.first + bi.get(nmaco[X[i]].front().second.second, INF32)) * T[X[i]]);
} else {
c -= maco * T[Y[i]];
if (nmaco[Y[i]].empty() || nmaco[Y[i]].back().first > c) {
while (!nmaco[Y[i]].empty() && nmaco[Y[i]].back().second.first == maco) nmaco[Y[i]].pop_back();
nmaco[Y[i]].emplace_back(c, make_pair(maco, B[i] + 1));
}
}
}
if (nmaco.back().empty()) return -1;
while (nmaco.back().size() > 1 && nmaco.back()[0].first + (nmaco.back()[0].second.first + bi.get(nmaco.back()[0].second.second, INF32)) * T.back() >= nmaco.back()[1].first + (nmaco.back()[1].second.first + bi.get(nmaco.back()[1].second.second, INF32)) * T.back()) nmaco.back().pop_front();
if (nmaco.back().front().first + co * T.back() >= INF) return -1;
return nmaco.back().front().first + co * T.back();
}
컴파일 시 표준 에러 (stderr) 메시지
train.cpp: In member function 'void BIT::add(ll)':
train.cpp:37:12: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for (; x < tree.size(); x += x & -x) tree[x]++;
| ~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |