| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 992349 | User0069 | 은하철도 (APIO24_train) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include"train.h"
#define taskname ""
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define int ll
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int maxn=5e5+3;
const int mod=1e9+7;
const int INF=1e9+1;
int ST[30*maxn];
int le[30*maxn],ri[30*maxn],cur;
int new_node()
{
++cur;
le[cur]=ri[cur]=-1;
ST[cur]=0;
return cur;
}
void update(int id,int cl,int cr,int pos,int val)
{
ST[id]+=val;
if(cl==cr)
{
return;
}
int mid=(cl+cr)/2;
if(pos<=mid)
{
if(le[id]==-1) le[id]==new_node();
update(le[id],cl,mid,pos,val);
}
else
{
if(ri[id]==-1) ri[id]=new_node();
update(ri[id],mid+1,cr,pos,val);
}
}
int get(int id,int cl,int cr,int l,int r)
{
if(id==-1) return 0;
if(cl>r||cr<l) return 0;
if(cl>=l&&cr<=r) return ST[id];
int mid=(cl+cr)/2;
return get(le[id],cl,mid,l,r)+get(ri[id],mid+1,cr,l,r);
}
struct train
{
int x,y,a,b,c;
};
bool operator <(train a,train b)
{
return a.b<b.b;
}
struct event
{
int type,l,r,a;
};
bool operator < (event a,event b)
{
if(a.r==b.r) return a.type<b.type;
return a.r<b.r;
}
map<int,int> dp[maxn];
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)
{
new_node();
vector<train> line;
vector<event> v;
set<int> s[n];
for(int i=0;i<m;i++)
{
line.push_back({x[i],y[i],a[i],b[i],c[i]});
s[x[i]].insert(a[i]);
s[y[i]].insert(b[i]);
}
s[n-1].insert(INF);
s[0].insert(0);
for(int i=0;i<w;i++)
{
v.push_back({1,l[i],r[i],0});
}
for(int i=0;i<n-1;i++)
{
int last=-1;
for(int x:s[i])
{
if(last!=-1)
{
v.push_back({2,last+1,x-1,i});
}
last=x;
}
}
sort(v.begin(),v.end());
for(event kk:v)
{
if(kk.type==1) update(1,0,INF,kk.l,1);
else
{
int siu=get(1,0,INF,kk.l,kk.r);
line.push_back({kk.a,kk.a,kk.l-1,kk.r+1,siu*t[kk.a]});
}
}
sort(line.begin(),line.end());
dp[0][0]=0;
for(train kk:line)
{
if(dp[kk.y].count(kk.b)==0) dp[kk.y][kk.b]=INF*INF;
if(dp[kk.x].count(kk.a)==0) dp[kk.x][kk.a]=INF*INF;
dp[kk.y][kk.b]=min(dp[kk.y][kk.b],dp[kk.a][kk.x]+kk.c);
}
if(dp[n-1].count(INF)==0) return -1;
else return dp[n-1][INF];
}
//signed main()
//{
// if (fopen(taskname".INP","r"))
// {
// freopen(taskname".INP","r",stdin);
// freopen(taskname".OUT","w",stdout);
// }
// Faster
//}