Submission #1162560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162560		alexander707070	Train (APIO24_train)	C++20	5 / 100	1100 ms	173100 KiB

train

#include<bits/stdc++.h>
#define MAXN 1000007
using namespace std;

const long long inf=1e18;
const int endt=1e9;

struct flight{
	int from,to;
	int l,r,cost;

	inline friend bool operator < (flight fr,flight sc){
		return fr.l<sc.l;
	}
}s[MAXN];

struct meal{
	int l,r;
}w[MAXN];

struct node{
	long long val,lazy;
};

struct Segment_tree{

	vector<node> tree;
	int lim;

	void init(int sz){
		lim=sz;

		tree.resize(4*sz+1);
		for(int i=1;i<=4*sz;i++)tree[i].val=inf;
	}

	void psh(int v){
		if(tree[v].lazy==0)return;

		tree[2*v].val+=tree[v].lazy;
		tree[2*v+1].val+=tree[v].lazy;

		tree[2*v].lazy+=tree[v].lazy;
		tree[2*v+1].lazy+=tree[v].lazy;

		tree[v].lazy=0;
	}

	long long getmin(int v,int l,int r,int ll,int rr){
		if(ll>rr)return inf;
		if(l==ll and r==rr)return tree[v].val;
		
		int tt=(l+r)/2;
		psh(v);

		return min( getmin(2*v,l,tt,ll,min(tt,rr)) , getmin(2*v+1,tt+1,r,max(tt+1,ll),rr) );
	}

	void setval(int v,int l,int r,int pos,long long s){
		if(l==r){
			tree[v].val=s;
		}else{
			int tt=(l+r)/2;
			psh(v);

			if(pos<=tt)setval(2*v,l,tt,pos,s);
			else setval(2*v+1,tt+1,r,pos,s);

			tree[v].val=min(tree[2*v].val,tree[2*v+1].val);
		}
	}

	void update(int v,int l,int r,int ll,int rr,long long s){
		if(ll>rr)return;

		if(l==ll and r==rr){
			tree[v].val+=s;
			tree[v].lazy+=s;
		}else{
			int tt=(l+r)/2;
			psh(v);

			update(2*v,l,tt,ll,min(tt,rr),s);
			update(2*v+1,tt+1,r,max(tt+1,ll),rr,s);

			tree[v].val=min(tree[2*v].val,tree[2*v+1].val);
		}
	}

	long long query(int l,int r){
		return getmin(1,1,lim,l,r);
	}

	void upd(int l,int r,long long s){
		update(1,1,lim,l,r,s);
	}

	void change(int pos,long long s){
		setval(1,1,lim,pos,s);
	}

}seg[MAXN];

int n,m,k,deg[MAXN],last[MAXN];
long long cost[MAXN];

long long dp[MAXN];

vector<int> times[MAXN];
priority_queue< pair<int,long long> , vector< pair<int,long long> > , greater< pair<int,long long> > > endf[MAXN];

unordered_map<int,int> compress[MAXN];

int compr(int val,int ver){
	int l=-1,r=deg[ver],tt;

	while(l+1<r){
		tt=(l+r)/2;
		if(times[ver][tt]<=val)l=tt;
		else r=tt;
	}

	return l+1;
}

long long meals(int l,int r){
	int res=0;
	for(int i=1;i<=k;i++){
		if(w[i].l>=l and w[i].r<=r)res++;
	}

	return res;
}

long long meals_ending(int l,int r){
	int res=0;

	for(int i=1;i<=k;i++){
		if(w[i].r>=l and w[i].r<=r)res++;
	}

	return res;
}

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; k=W;

	for(int i=1;i<=n;i++)cost[i]=T[i-1];

	deg[1]=1;
	times[1]={0};

	for(int i=1;i<=m;i++){
		s[i]={X[i-1]+1,Y[i-1]+1,A[i-1],B[i-1],C[i-1]};

		deg[s[i].to]++;
		times[s[i].to].push_back(s[i].r);
	}

	sort(s+1,s+m+1);

	for(int i=1;i<=n;i++){
		
		sort(times[i].begin(),times[i].end());

		for(int f=0;f<times[i].size();f++){
			compress[i][times[i][f]]=f+1;
		}

		seg[i].init(deg[i]);
		last[i]=0;
	}
	seg[1].change(1,0);

	for(int i=1;i<=k;i++)w[i]={L[i-1],R[i-1]};

	for(int i=1;i<=m;i++){
		dp[i]=inf;

		if(last[s[i].from]!=s[i].l-1){
			seg[s[i].from].upd(1,deg[s[i].from] , meals_ending(last[s[i].from]+1,s[i].l-1) * cost[s[i].from] );
			last[s[i].from]=s[i].l-1;
		}

		while(!endf[s[i].from].empty() and endf[s[i].from].top().first<=s[i].l){
			
			auto curr=endf[s[i].from].top();
			seg[s[i].from].change(compress[s[i].from][curr.first],curr.second + meals(curr.first,s[i].l-1) * cost[s[i].from]);

			endf[s[i].from].pop();
		}
		
		int to=compr(s[i].l,s[i].from);

		long long mindp=seg[s[i].from].query(1,to);
		dp[i]=mindp+s[i].cost;

		endf[s[i].to].push({s[i].r,dp[i]});
	}

	long long ans=inf;
	for(int i=1;i<=m;i++){
		if(s[i].to!=n)continue;

		ans=min(ans , dp[i] + meals(s[i].r+1,endt) * cost[n]);
	}

	if(ans>=inf)return -1;
	return ans;
}   

/*int main(){

	cout<<solve(3, 3, 1, {20, 30, 40}, {0, 1, 0}, {1, 2, 2},
		{1, 20, 18}, {15, 30, 40}, {10, 5, 40}, {16}, {19})<<"\n";	   

	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})<<"\n";

	return 0;
}*/

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