제출 #1162823

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1162823		alexander707070	은하철도 (APIO24_train)	C++20	0 / 100	307 ms	92704 KiB

train

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

const long long inf=1e18;

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];

int n,m,k,cnt;
long long cost[MAXN],dp[MAXN];
priority_queue< pair<int,long long> , vector< pair<int,long long> > , greater< pair<int,long long> > > endf[MAXN];

vector<int> vals,z[5*MAXN];
unordered_map<int,int> mp;

struct PST{
	struct node{
		int l,r;
		int val;
	};

	int top[5*MAXN],num;
	node tree[100*MAXN];

	int update(int v,int l,int r,int pos){
		if(l==r){
			num++; 
			tree[num].val=tree[v].val+1;

			return num;
		}else{
			int tt=(l+r)/2;

			int ll=tree[v].l,rr=tree[v].r;
			if(pos<=tt){
				ll=update(tree[v].l,l,tt,pos);
			}else{
				rr=update(tree[v].r,tt+1,r,pos);
			}

			num++;
			tree[num]={ll,rr,0};
			tree[num].val=tree[tree[num].l].val + tree[tree[num].r].val;

			return num;
		}
	}

	int getdiff(int v1,int v2,int l,int r,int ll,int rr){
		if(ll>rr)return 0;
		if(l==ll and r==rr)return tree[v2].val-tree[v1].val;

		int tt=(l+r)/2;
		return getdiff(tree[v1].l,tree[v2].l,l,tt,ll,min(tt,rr)) + getdiff(tree[v1].r,tree[v2].r,tt+1,r,max(tt+1,ll),rr);
	}
}seg;

long long meals(int l,int r){
	if(l>r)return 0;

	return seg.getdiff(seg.top[l-1],seg.top[r],1,cnt,l,r);
}

struct Li_Chao{

	struct state{
		long long bias;
		int l;
	};

	set<int> vals;

	vector<int> xs;
	vector<state> tree;
	long long coef;

	int sz;

	void init(){
		sz=int(vals.size());

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

		for(int i:vals)xs.push_back(i);
	}

	bool better(state a,state b,int x){
		if(x<a.l and x<b.l){
			return a.l<b.l;
		}else if(x<a.l)return false;
		else if(x<b.l)return true;	

		else return a.bias + meals(a.l,x)*coef < b.bias + meals(b.l,x)*coef;
	}

	void add(int v,int l,int r,state s){
		if(better(s,tree[v],xs[l]) and better(s,tree[v],xs[r]))swap(s,tree[v]);
		if(l==r)return;

		int tt=(l+r)/2;
		if(better(s,tree[v],xs[l]))add(2*v,l,tt,s);
		if(better(s,tree[v],xs[r]))add(2*v+1,tt+1,r,s);
	}

	void upd(state s){
		add(1,0,sz-1,s);
	}

	long long query(int v,int l,int r,int pos){
		if(l==r)return tree[v].bias + meals(tree[v].l,xs[pos]) * coef;

		int tt=(l+r)/2;
		if(pos<=tt)return min( tree[v].bias + meals(tree[v].l,xs[pos]) * coef , query(2*v,l,tt,pos) );
		else return min( tree[v].bias + meals(tree[v].l,xs[pos]) * coef , query(2*v+1,tt+1,r,pos) );
	}

	long long ask(int x){
		int l=0,r=sz,tt;
		while(l+1<r){
			tt=(l+r)/2;
			if(xs[tt]<=x)l=tt;
			else r=tt;
		}

		return query(1,0,sz-1,l);
	}

}cht[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){
	n=N; m=M; k=W;

	vals.push_back(0);
	for(int i=1;i<=m;i++){
		vals.push_back(A[i-1]-1);
		vals.push_back(A[i-1]);
		vals.push_back(B[i-1]);
	}

	for(int i=1;i<=k;i++){
		vals.push_back(L[i-1]);
		vals.push_back(R[i-1]);
	}

	sort(vals.begin(),vals.end());

	for(int i=0;i<vals.size();i++){
		if(i==0 or vals[i]!=vals[i-1])cnt++;
		mp[vals[i]]=cnt;
	}

	for(int i=1;i<=m;i++){
		A[i-1]=mp[A[i-1]];
		B[i-1]=mp[B[i-1]];
	}

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

	for(int i=1;i<=n;i++){
		cost[i]=T[i-1];
		cht[i].coef=cost[i];
	}

	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]};

		cht[s[i].from].vals.insert(s[i].l-1);
	}

	for(int i=1;i<=k;i++){
		z[L[i-1]].push_back(R[i-1]);
	}

	for(int i=1;i<=cnt;i++){
		int curr=seg.top[i-1];

		for(int f:z[i]){
			seg.top[i]=seg.update(curr,1,cnt,f);
			curr=seg.top[i];
		}

		seg.top[i]=curr;
	}

	sort(s+1,s+m+1);
	for(int i=1;i<=n;i++)cht[i].init();

	cht[1].upd({0,1});

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

		while(!endf[s[i].from].empty() and endf[s[i].from].top().first<=s[i].l){
			
			auto curr=endf[s[i].from].top();
			cht[s[i].from].upd({curr.second,curr.first});
			endf[s[i].from].pop();
		}

		long long mindp=cht[s[i].from].ask(s[i].l-1);
		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,cnt) * 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: 0 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60