#include "train.h"
#include <bits/stdc++.h>
using namespace std;
#define rng(i,a,b) for(int i=int(a);i<=int(b);i++)
#define rep(i,b) rng(i,0,b-1)
#define gnr(i,b,a) for(int i=int(b);i>=int(a);i--)
#define per(i,b) gnr(i,b-1,0)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
typedef long long ll;
using pii=pair<int,int>;
using vi=vc<int>;
using uint=unsigned;
using ull=unsigned long long;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using t3=tuple<int,int,int>;
#define N_ 401000
struct Edge{
int x, y, a, b, c;
};
struct rangeCounter{
vc<pii>LR;
struct Node{
int l, r, s;
};
vc<Node>T;
vi Root;
int cnt, N;
void Add(int nd, int p, int b, int e, int x){
T[nd] = T[p];
T[nd].s++;
if(b==e)return;
int m = (b+e)>>1;
if(x<=m){
T[nd].l = ++cnt;
Add(T[nd].l, T[p].l, b,m,x);
}
else{
T[nd].r = ++cnt;
Add(T[nd].r, T[p].r, m+1,e,x);
}
}
void init(int NN, vi &L, vi &R){
LR.clear();
cnt = 0;
N = NN;
int M = si(L);
rep(i,M){
LR.pb({L[i],R[i]});
}
sort(all(LR));
Root.resize(M+1);
T.resize(M*30);
rep(i,M){
Root[i+1] = ++cnt;
Add(Root[i+1],Root[i], 0, N ,LR[i].se);
}
}
int Sum(int nd, int b, int e, int r){
if(b>r)return 0;
if(e<=r)return T[nd].s;
int m = (b+e)>>1;
if(r<=m)return Sum(T[nd].l,b,m,r);
else return T[T[nd].l].s + Sum(T[nd].r, m+1,e,r);
}
int Get(int l, int r){
int pv = lower_bound(all(LR), pii(l,-1)) - LR.begin();
return Sum(Root.back(), 0, N, r) - Sum(Root[pv], 0, N, r);
}
}RC;
int TM;
ll INF = 1e18;
struct dp{
vc<pil> Q;
vi OV;
int head, price;
dp(){
Q.clear();
OV.clear();
head=price=0;
}
ll getValue(pil p, int t){
return p.se + price * RC.Get(p.fi+1, t);
}
int Over(pil p1, pil p2){ // p1.t < p2.t
int b = p2.fi+1, e = TM-1, r=TM;
while(b<=e){
int mid = (b+e)>>1;
if(getValue(p1,mid) >= getValue(p2,mid)){
r=mid;
e=mid-1;
}
else b=mid+1;
}
return r;
}
void Put(int t, ll cost){
while(head < si(Q) && Q.back().se >= cost){
Q.pop_back();
OV.pop_back();
}
if(head < si(Q) && Q.back().fi == t)return;
int tp=0;
while(head < si(Q)-1){
int pv = si(Q)-1;
if(tp <= OV[pv]){
Q.pop_back();
OV.pop_back();
}
else break;
}
Q.pb({t,cost});
if(head < si(Q)-1){
OV.pb(Over(Q[si(Q)-2],Q[si(Q)-1]));
}
else OV.pb(0);
}
ll Get(int t){
while(head < si(Q)-1 && OV[head+1] <= t-1) head++;
if(head >= si(Q))return INF;
return getValue(Q[head],t-1);
}
};
long long solve(int N, int M, int W, std::vector<int> T, std::vector<int> X, std::vector<int> Y,
std::vector<int> A, std::vector<int> B, std::vector<int> C, std::vector<int> L,
std::vector<int> R) {
vi Z;
rep(i,M){
Z.pb(A[i]);
Z.pb(B[i]);
}
rep(i,W){
Z.pb(L[i]);
Z.pb(R[i]);
}
sort(all(Z));
auto ReNum = [&](vi &z, int &t) -> void {
t = (lower_bound(all(z),t)-z.begin()) + 1;
};
rep(i,M){
ReNum(Z,A[i]);
ReNum(Z,B[i]);
}
rep(i,W){
ReNum(Z,L[i]);
ReNum(Z,R[i]);
}
TM = si(Z) + 1;
RC.init(TM, L, R);
vc<vc<Edge>> O(TM);
vc<vc<pil>>UDT(TM);
/*rep(i,W){
printf("%d %d\n",L[i],R[i]);
}
puts("");*/
rep(i,M){
//printf("%d %d %d %d %d\n",X[i],Y[i],A[i],B[i],C[i]);
O[A[i]].pb({X[i],Y[i],A[i],B[i],C[i]});
}
vc<dp> D(N);
rep(i,N)D[i].price = T[i];
D[0].Put(0,0);
rep(i,TM){
for(auto &[y,cost]: UDT[i]){
D[y].Put(i,cost);
}
for(auto &[x,y,a,b,c]: O[i]){
ll g = D[x].Get(a);
if(g<INF){
//printf("%d %d %lld\n",y,b,g+c);
UDT[b].pb({y,g+c});
}
}
}
return D[N-1].Get(TM);
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
604 KB |
Correct. |
| 2 |
Incorrect |
1 ms |
604 KB |
Wrong Answer. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
69 ms |
36548 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
69 ms |
36548 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
604 KB |
Correct. |
| 2 |
Incorrect |
1 ms |
604 KB |
Wrong Answer. |
| 3 |
Halted |
0 ms |
0 KB |
- |
