제출 #993034

#제출 시각아이디문제언어결과실행 시간메모리
993034Programmer123은하철도 (APIO24_train)C++17
5 / 100
420 ms189564 KiB
#include "train.h" #include <bits/stdc++.h> namespace Kth { struct Wavelet { int min, max; std::vector<int> pfx; Wavelet *left, *right; Wavelet(int l, int r, std::vector<int> &stuff) : min(l), max(r) { if (stuff.empty()) return; if (max == min + 1) { left = right = nullptr; return; } int mid = (min + max) / 2; int s = 0; std::vector<int> L, R; for (auto x: stuff) { if (x < mid) { s++; L.push_back(x); } else { R.push_back(x); } pfx.push_back(s); } stuff.clear(); left = new Wavelet(min, mid, L); right = new Wavelet(mid, max, R); } int query(int l, int r, int k) {//Return value of kth (0-indexed) largest in [l,r] if (max == min + 1) return min; int numInRange = pfx[r]; if (l) numInRange -= pfx[l]; if (numInRange > k) { return left->query(l ? pfx[l - 1] : 0, r ? pfx[r - 1] : 0, k); } else { return right->query(l ? l - pfx[l - 1] : 0, r ? r - pfx[r - 1] : 0, k); } } }; } struct Compressor { std::vector<int> stuff; std::map<int, int> res; void run() { std::sort(stuff.begin(), stuff.end()); stuff.erase(std::unique(stuff.begin(), stuff.end()), stuff.end()); for (int i = 0; i < stuff.size(); ++i) { res[stuff[i]] = i; } stuff.clear(); } void operator+=(int x) { stuff.push_back(x); } int operator[](int x) { return res[x]; } }; struct node { int min, max; node *left, *right; int value; node(int l, int r) { min = l; max = r; left = right = nullptr; value = 0; } void add(int l, int r) { l = std::max(l, min); r = std::min(r, max); if (l >= max || r <= min) return; if (l == min && r == max) { value++; return; } if (!left) { left = new node(min, (min + max) / 2); right = new node((min + max) / 2, max); } left->add(l, r); right->add(l, r); } int query(int x) const { if (x < min || x >= max) return 0; return value + (left ? (left->query(x) + right->query(x)) : 0); } }; struct countnode { int min, max; countnode *left, *right; int value; countnode(int l, int r) { min = l; max = r; left = right = nullptr; value = 0; } void add(int x) { if (x < min || x >= max) return; value++; if (max == min + 1) return; if (!left) { left = new countnode(min, (min + max) / 2); right = new countnode((min + max) / 2, max); } left->add(x); right->add(x); } int query(int l, int r) const { l = std::max(l, min); r = std::min(r, max); if (l >= max || r <= min) return 0; if (l == min && r == max) return value; if (!left) return 0; return left->query(l, r) + right->query(l, r); } }; long long solve(int nodes, int edges, int meals, std::vector<int> mealCost, std::vector<int> start, std::vector<int> end, std::vector<int> startTime, std::vector<int> endTime, std::vector<int> cost, std::vector<int> mealStart, std::vector<int> mealEnd) { { Compressor c; c += -1; for (int i = 0; i < edges; ++i) { c += startTime[i]; c += endTime[i]; } for (int i = 0; i < meals; ++i) { c += mealStart[i]; c += mealEnd[i]; } c.run(); for (int i = 0; i < edges; ++i) { startTime[i] = c[startTime[i]]; endTime[i] = c[endTime[i]]; } for (int i = 0; i < meals; ++i) { mealStart[i] = c[mealStart[i]]; mealEnd[i] = c[mealEnd[i]]; } } //All times are now in [0, 400000] node tree(0, 400001); countnode countTree(0, 400001); for (int i = 0; i < meals; ++i) { countTree.add(mealStart[i]); } std::vector<std::pair<int, int>> stuff; for (int i = 0; i < meals; ++i) { stuff.emplace_back(mealStart[i], mealEnd[i]); } std::sort(stuff.begin(), stuff.end()); std::vector<int> Stuff; for (auto [a, b]: stuff) { Stuff.push_back(b); } Kth::Wavelet kth(0, 400001, Stuff); std::deque<std::pair<int, long long>> current[nodes];//{pos, cost} current[0].emplace_back(0, 0); struct event { int time; int idx; bool departure; bool meal; }; std::vector<event> events; for (int i = 0; i < edges; ++i) { events.push_back({startTime[i], i, true, false}); events.push_back({endTime[i], i, false, false}); } for (int i = 0; i < meals; ++i) { events.push_back({mealEnd[i], i, false, true}); } std::sort(events.begin(), events.end(), [&](event a, event b) { if (a.time == b.time && a.meal == b.meal) return a.departure < b.departure; if (a.time == b.time) return a.meal < b.meal; return a.time < b.time; }); auto overTake = [&](int p1, int p2, long long diff, int cost) {//Diff = cost[p2]-cost[p1] if (diff <= 0) return 0; if (p1 == p2) return INT_MAX; if (cost == 0) return INT_MAX; long long needed = (diff + cost - 1) / cost;//As soon as *at least* needed, go if (countTree.query(p1 + 1, p2 + 1) < needed) return INT_MAX; int lidx = countTree.query(0, p1 + 1); int ridx = countTree.query(0, p2 + 1) - 1; return kth.query(lidx, ridx, needed - 1); }; auto score = [&](int p, long long c, int node) { return c + ((long long) tree.query(p)) * mealCost[node]; }; const long long INF = LONG_LONG_MAX / 2; auto getBest = [&](int node) { while (current[node].size() > 1 && score(current[node][0].first, current[node][0].second, node) >= score(current[node][1].first, current[node][1].second, node)) { current[node].pop_front(); } if (current[node].empty()) return INF; return score(current[node][0].first, current[node][0].second, node); }; auto add = [&](int node, int p, long long c) { while (((!current[node].empty()) && score(p, c, node) <= score(current[node].back().first, current[node].back().second, node)) || (current[node].size() > 1 && overTake(p, current[node].back().first, c - current[node].back().second, mealCost[node]) <= overTake(current[node][current[node].size() - 2].first, current[node].back().first, current[node].back().second - current[node][current[node].size() - 2].second, mealCost[node]))) { current[node].pop_back(); } current[node].emplace_back(p, c); }; long long edgeTime[edges]; for (auto [time, idx, depart, meal]: events) { if (meal) { tree.add(0, mealStart[idx]); } else if (depart) { edgeTime[idx] = getBest(start[idx]); if (edgeTime[idx] != INF) { edgeTime[idx] += cost[idx]; } } else { if (edgeTime[idx] != INF) add(end[idx], time, edgeTime[idx]); // current[end[idx]].emplace_back(time, edgeTime[idx]); } } auto res = getBest(nodes - 1); if (res == INF) return -1ll; return res; }

컴파일 시 표준 에러 (stderr) 메시지

train.cpp: In member function 'void Compressor::run()':
train.cpp:53:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for (int i = 0; i < stuff.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...