제출 #992365

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
992365		User0069	은하철도 (APIO24_train)	C++17	5 / 100	256 ms	116684 KiB

train

#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(int32_t n,int32_t m,int32_t w,vector<int32_t> t,vector<int32_t> x,vector<int32_t> y,vector<int32_t> a,vector<int32_t> b,vector<int32_t> c,vector<int32_t> l,vector<int32_t> 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;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.x][kk.a]+kk.c);
//        cout<<kk.x<<" "<<kk.y<<" "<<kk.a<<" "<<kk.b<<" "<<kk.c<<"\n";
    }
//    for(int i=0;i<n;i++)
//    {
//        for(pii kk:dp[i])
//        {
//            cout<<kk.first<<" "<<kk.second<<" ; ";
//        }
//        cout<<"\n";
//    }
    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
//    cout<<solve(3, 5, 6, {30, 38, 33}, {0, 1, 0, 0, 1}, {2, 0, 1, 2, 2},
// {12, 48, 26, 6, 49}, {16, 50, 28, 7, 54}, {38, 6, 23, 94, 50},
// {32, 14, 42, 37, 2, 4}, {36, 14, 45, 40, 5, 5});
//}

• Subtask 1: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60