Submission #991296

#	Time	Username	Problem	Language	Result	Execution time	Memory
991296		amirhoseinfar1385	Train (APIO24_train)	C++17	100 / 100	682 ms	311672 KiB

train

//khodaya komak kon
#include "train.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10,maxw=maxn*4;
vector<int>allind;
long long n,m,w,allt[maxn];
long long inf=1e17;
int dproot[maxw];

int kaf=(1<<19),root=0;
struct segment{
    struct node{
        int rc,lc,w;
        node(){
            rc=lc=w=0;
        }
    };
    int ts=(1<<20);
    node seg[(1<<20)*20];
    segment(){
        for(int i=1;i<kaf;i++){
            seg[i].rc=((i<<1)^1);
            seg[i].lc=(i<<1);
        }
    }
    int upd(int i,int l,int r,int tl,int tr,int w){
        if(l>r||l>tr||r<tl||tl>tr){
            return i;
        }
        if(l>=tl&&r<=tr){
            seg[ts]=seg[i];
            seg[ts].w+=w;
            ts++;
            return ts-1;
        }
        int m=(l+r)>>1;
        int fts=ts;
        ts++;
        seg[fts]=seg[i];
        seg[fts].lc=upd(seg[fts].lc,l,m,tl,tr,w);
        seg[fts].rc=upd(seg[fts].rc,m+1,r,tl,tr,w);
        return fts;
    }
    int pors(int i,int l,int r,int tl,int tr){
        int ret=0;
        while(true){
            ret+=seg[i].w;
            if(l>=tl&&r<=tr){
                return ret;
            }
            int m=(l+r)>>1;
            if(tl<=m){
                i=seg[i].lc;
                r=m;
            }else{
                i=seg[i].rc;
                l=m+1;
            }
           // return pors(seg[i].rc,m+1,r,tl,tr)+pors(seg[i].lc,l,m,tl,tr)+seg[i].w;
        }
    }
}seg;

struct func{
    long long x0,w,ind;
    func(){
        x0=0;
        ind=0;
        w=inf;
    }
    long long get(long long inda){
        inda=min(inda,(long long)allind.size()-1);
        if(inda<x0){
            return w;
        }
        //cout<<"wtf: "<<allind[x0]<<" "<<allind[inda]<<" "<<seg.pors(dproot[x0+1],0,kaf-1,inda,inda)<<endl;
        return w+allt[ind]*seg.pors(dproot[x0+1],0,kaf-1,inda,inda);
    }
    bool operator ==(func f){
        return (f.x0==x0&&f.w==w);
    }
}fakefunc;
 
struct lichao{
    struct node{
        int l,r;
        node(){
            l=r=-1;
        }
        func f;
    };
    vector<node> segl;
    void create(int sz){
        sz+=2;
        segl.resize(sz);
    }
    int te=1;
    int gor(int i){
        if(segl[i].r==-1){
            segl[i].r=te;
            te++;
        }
        return segl[i].r;
    }
    int gol(int i){
        if(segl[i].l==-1){
            segl[i].l=te;
            te++;
        }
        return segl[i].l;
    }
    void add(func f,int i=0,int l=0,int r=1e6){
        if(l==r){
            return ;
        }
        if(segl[i].f==fakefunc){
            segl[i].f=f;
            return ;
        }
        int m=(l+r)/2;
        if(segl[i].f.get(l)>f.get(l)){
            swap(segl[i].f,f);
        }
        if(l==r-1){
            return ;
        }
        if(segl[i].f.get(m)<=f.get(m)){
            add(f,gor(i),m,r);
        }else{
            swap(segl[i].f,f);
            add(f,gol(i),l,m);
        }
    }
    long long pors(int w,int i=0,int l=0,int r=1e6){
        if(l==r){
            return 0;
        }
        long long ret=segl[i].f.get(w);
        long long m=(l+r)>>1;
        if(w>=m&&segl[i].r!=-1){
            ret=min(ret,pors(w,segl[i].r,m,r));
        }
        if(w<m&&segl[i].l!=-1){
            ret=min(ret,pors(w,segl[i].l,l,m));
        }
        return ret;
    }
}lich[maxn];

struct yal{
    int u,v,l,r,w;
}alle[maxn];
vector<int>adj[maxw];
int cnt[maxn];
vector<pair<int,int>>allw;
vector<int>allwi[maxw];
vector<func>addy[maxw];
void preq(){
    for(auto x:allw){
        allwi[x.first].push_back(x.second);
    }
    for(long long i=maxw-1;i>=0;i--){
        for(auto x:allwi[i]){
            root=seg.upd(root,0,kaf-1,x,(int)allind.size(),1);
        }
        dproot[i]=root;
    }
}

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) {
	n=N;
    m=M;
    w=W;
    for(int i=0;i<n;i++){
        allt[i]=T[i];
    }
    allind.push_back(0);
    for(int i=0;i<m;i++){
        allind.push_back(A[i]);
        allind.push_back(B[i]);
    }
    for(int i=0;i<w;i++){
        allind.push_back(L[i]);
        allind.push_back(R[i]);
    }
    sort(allind.begin(),allind.end());
    allind.resize(unique(allind.begin(),allind.end())-allind.begin());
    for(int i=0;i<m;i++){
        A[i]=lower_bound(allind.begin(),allind.end(),A[i])-allind.begin();
        B[i]=lower_bound(allind.begin(),allind.end(),B[i])-allind.begin();
    }
    for(int i=0;i<w;i++){
        L[i]=lower_bound(allind.begin(),allind.end(),L[i])-allind.begin();
        R[i]=lower_bound(allind.begin(),allind.end(),R[i])-allind.begin();
        allw.push_back(make_pair(L[i],R[i]));
    }
    preq();
    for(int i=0;i<m;i++){
        alle[i].u=X[i];
        alle[i].v=Y[i];
        alle[i].w=C[i];
        alle[i].l=A[i];
        alle[i].r=B[i];
        cnt[alle[i].v]++;
    //    //cout<<"wtf "<<alle[i].l<<endl;
        adj[alle[i].l].push_back(i);
    //    //cout<<"nago"<<endl;
    }
    for(int i=0;i<n;i++){
    //    //cout<<"injy"<<endl;
        lich[i].create(cnt[i]);
    //    //cout<<"oonjy"<<endl;
        func f;
        if(i==0){
            f.w=0;
        }else{
            f.w=inf;
        }
    //    //cout<<"salam"<<endl;
        f.x0=0;
        f.ind=i;
        lich[i].add(f);
    //    //cout<<"by"<<endl;
    }
    ////cout<<"salam"<<endl;
    for(int i=0;i<maxw;i++){
        for(auto x:addy[i]){
            lich[x.ind].add(x);
        }
        for(auto x:adj[i]){
            long long w=lich[alle[x].u].pors(alle[x].l-1);
            w+=alle[x].w;
            //cout<<"pors: "<<alle[x].u<<" "<<alle[x].v<<" "<<allind[alle[x].l]<<" "<<allind[alle[x].r]<<" "<<alle[x].w<<" "<<w<<endl;
            func f;
            f.ind=alle[x].v;
            f.w=w;
            f.x0=alle[x].r;
            addy[alle[x].r].push_back(f);
        }
    }
    if(lich[n-1].pors(maxw+1)>=inf){
        return -1;
    }
    return lich[n-1].pors(maxw+1);
}

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