| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 995243 |
2024-06-08T17:29:04 Z |
huutuan |
Train (APIO24_train) |
C++17 |
|
123 ms |
127280 KB |
#include "train.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10, S=500, inf=1e18;
struct Node{
int val, lazy;
Node (int _val=0){
val=_val, lazy=0;
}
Node operator+(const Node &a){
return Node(min(val, a.val));
}
};
struct SegmentTree{
int n;
vector<Node> t;
void init(int _n, int val=0){
n=_n;
t.assign(4*n+1, Node(val));
t[0]=Node(inf);
}
void apply(int k, int val){
t[k].val+=val;
t[k].lazy+=val;
}
void push(int k){
if (t[k].lazy){
apply(k<<1, t[k].lazy);
apply(k<<1|1, t[k].lazy);
t[k].lazy=0;
}
}
void update(int k, int l, int r, int L, int R, int val){
if (r<L || R<l) return;
if (L<=l && r<=R){
apply(k, val);
return;
}
push(k);
int mid=(l+r)>>1;
update(k<<1, l, mid, L, R, val);
update(k<<1|1, mid+1, r, L, R, val);
t[k]=t[k<<1]+t[k<<1|1];
}
Node get(int k, int l, int r, int L, int R){
if (r<L || R<l) return t[0];
if (L<=l && r<=R) return t[k];
push(k);
int mid=(l+r)>>1;
return get(k<<1, l, mid, L, R)+get(k<<1|1, mid+1, r, L, R);
}
} st;
struct State{
int u, time, type;
State (int _u=0, int _time=0, int _type=0){
u=_u, time=_time, type=_type;
}
bool operator<(const State &a){
return tie(u, time, type)<tie(a.u, a.time, a.type);
}
bool operator==(const State &a){
return tie(u, time, type)==tie(a.u, a.time, a.type);
}
};
vector<State> vs;
vector<int> vt;
int n, m, cost[N], heavy[N];
vector<pair<int, int>> g[N];
vector<int> vv[N];
int f[N], vis[N];
vector<pair<int, pair<int, int>>> query[N];
vector<int> add[N];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
void process_heavy(int u){
st.init((int)vt.size(), inf);
for (int i=1; i<(int)vv[u].size(); i+=2) st.update(1, 1, st.n, vs[vv[u][i]].time, vs[vv[u][i]].time, f[vv[u][i]]-inf);
for (int i=0, j=0; i<(int)vt.size(); ++i){
for (int k:add[i]) st.update(1, 1, st.n, 1, k, cost[u]);
while (j<(int)vv[u].size() && (vs[vv[u][j]].time<i)) j+=2;
if (j>=(int)vv[u].size()) break;
if (vs[vv[u][j]].time==i){
f[vv[u][j]]=min(f[vv[u][j]], st.get(1, 1, st.n, 1, i).val);
pq.emplace(f[vv[u][j]], vv[u][j]);
}
}
}
long long solve(int32_t N_, int32_t M, int32_t W, std::vector<int32_t> T, std::vector<int32_t> X, std::vector<int32_t> Y,
std::vector<int32_t> A, std::vector<int32_t> B, std::vector<int32_t> C, std::vector<int32_t> L,
std::vector<int32_t> R) {
n=N_, m=M;
for (int i=0; i<n; ++i) cost[i]=T[i];
for (int i=0; i<W; ++i){
vt.push_back(L[i]);
vt.push_back(R[i]);
}
vt.push_back(-1);
vt.push_back(0); vt.push_back(1e9);
sort(vt.begin(), vt.end()); vt.resize(unique(vt.begin(), vt.end())-vt.begin());
st.init((int)vt.size());
for (int i=0; i<W; ++i){
L[i]=lower_bound(vt.begin(), vt.end(), L[i])-vt.begin();
R[i]=lower_bound(vt.begin(), vt.end(), R[i])-vt.begin();
}
for (int i=0; i<m; ++i){
A[i]=lower_bound(vt.begin(), vt.end(), A[i])-vt.begin();
B[i]=upper_bound(vt.begin(), vt.end(), B[i])-vt.begin()-1;
vs.emplace_back(X[i], A[i], 0);
vs.emplace_back(X[i], A[i], 1);
vs.emplace_back(Y[i], B[i], 0);
vs.emplace_back(Y[i], B[i], 1);
}
vs.emplace_back(0, 1, 0);
vs.emplace_back(0, 1, 1);
vs.emplace_back(n-1, (int)vt.size()-1, 0);
vs.emplace_back(n-1, (int)vt.size()-1, 1);
sort(vs.begin(), vs.end()); vs.resize(unique(vs.begin(), vs.end())-vs.begin());
for (int i=0; i<m; ++i){
int i1=lower_bound(vs.begin(), vs.end(), State(X[i], A[i], 0))-vs.begin();
int i2=lower_bound(vs.begin(), vs.end(), State(Y[i], B[i], 1))-vs.begin();
g[i1].emplace_back(i2, C[i]);
}
for (int i=0; i<(int)vs.size(); ++i) vv[vs[i].u].push_back(i);
for (int i=0; i<n; ++i) heavy[i]=(int)vv[i].size()>=S, f[i]=inf;
for (int i=0; i<n; ++i) if (!heavy[i]){
for (int j=1; j<(int)vv[i].size(); j+=2) for (int k=j-1; k<(int)vv[i].size(); k+=2){
query[vs[vv[i][k]].time].push_back({vs[vv[i][j]].time, {vv[i][j], (int)g[vv[i][j]].size()}});
g[vv[i][j]].emplace_back(vv[i][k], 0);
}
}
for (int i=0; i<W; ++i) add[R[i]+1].push_back(L[i]-1);
for (int i=0; i<(int)vt.size(); ++i){
for (int j:add[i]) st.update(1, 1, st.n, 1, j, 1);
for (auto &j:query[i]) g[j.second.first][j.second.second].second=st.get(1, 1, st.n, j.first, j.first).val*cost[vs[j.second.first].u];
}
for (int i=0; i<N; ++i) f[i]=inf;
// for (int i=0; i<N; ++i) for (auto &e:g[i]){
// int j=e.first, w=e.second;
// cout << vs[i].u << ' ' << vt[vs[i].time] << ' ' << vs[i].type << ' ' << vs[j].u << ' ' << vt[vs[j].time] << ' ' << vs[j].type << ' ' << w << '\n';
// }
f[1]=0;
process_heavy(0);
vector<int> qq;
while (pq.size()){
while (pq.size()){
int u=pq.top().second, d=pq.top().first;
pq.pop();
if (f[u]!=d) continue;
for (auto &e:g[u]){
int v=e.first, w=e.second;
if (f[v]>d+w){
f[v]=d+w;
if (heavy[vs[v].u]){
if (!vis[vs[v].u]){
vis[vs[v].u]=1;
qq.push_back(vs[v].u);
}
}else pq.emplace(f[v], v);
}
}
}
for (int u:qq) process_heavy(u);
qq.clear();
}
int ans=f[(int)vs.size()-2];
if (ans==inf) ans=-1;
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
107612 KB |
Correct. |
| 2 |
Correct |
19 ms |
107544 KB |
Correct. |
| 3 |
Incorrect |
24 ms |
107612 KB |
Wrong Answer. |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
123 ms |
127280 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
123 ms |
127280 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
107612 KB |
Correct. |
| 2 |
Correct |
19 ms |
107544 KB |
Correct. |
| 3 |
Incorrect |
24 ms |
107612 KB |
Wrong Answer. |
| 4 |
Halted |
0 ms |
0 KB |
- |
