Submission #1200234

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200234		justinlgl20	Train (APIO24_train)	C++20	40 / 100	371 ms	85364 KiB

train

#include <bits/stdc++.h>
#include "train.h"
using namespace std;
 
#define int long long
 
#define all(x) (x).begin(), (x).end()
 
template<template<typename> class Container, typename G>
ostream& operator<<(ostream& os, Container<G> x) {
    int f = 0; os << '{'; for (auto &i: x) os << (f++ ? ", " : ""), os << i; os << "}";
    return os;
}
 
void _print() {cerr << "]\n";}
 
template<typename T, typename... V>
void _print(T t, V... v) {cerr << t; if (sizeof...(v)) cerr <<", "; _print(v...);}
 
#ifdef DEBUG
#define dbg(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif

#define pii pair<int, int>
#define f first
#define s second

const int INF=1e18;

struct path{
	int a,b,u,v,c,inx;//u->v
	path(){inx=0;};
	bool operator<(path other){
		return b>other.b;
	}
};

struct wavelet{
	int tl,tr;wavelet *l,*r;vector<int> b;
	wavelet(){}
	wavelet(int *from,int *to,int x,int y){
		tl=x,tr=y;
		if(tl==tr or from>=to)return;
		int tm=(tl+tr)>>1;
		auto f=[tm](int x){return x<=tm;};
		b.reserve(to-from+1);
		b.push_back(0);
		for(auto it=from;it!=to;it++){
			b.push_back(b.back()+f(*it));
		}
		auto pivot=stable_partition(from,to,f);
		l=new wavelet(from,pivot,tl,tm);
		r=new wavelet(pivot,to,tm+1,tr);
	}
	int LTE(int l,int r,int k){
		if(l>r or k<tl)return 0;
		if(tr<=k)return r-l+1;
		int lb=b[l-1],rb=b[r];
		return this->l->LTE(lb+1ll,rb,k)+this->r->LTE(l-lb,r-rb,k);
	}
	~wavelet(){
		delete l;delete r;
	}
};

// need range inside queries in log, so we use pseg or merge sort tree
template<int sz>
struct interval{
	vector<pii> v;
	wavelet *t;
	int a[sz];
	void init(){
		v.clear();
		delete t;
	}
	void add(int l,int r){
		v.emplace_back(l,r);
	}
	void process(){
		sort(all(v));
		for(int i=0;i<v.size();i++)a[i]=v[i].s;
		t=new wavelet(a,a+v.size(),0,sz);
	}
	int query(int l,int r){
		int inx=lower_bound(all(v),make_pair(l,0ll))-v.begin();int inx2=upper_bound(all(v),make_pair(r,INF))-v.begin()-1;
		int ans=t->LTE(inx+1,inx2+1,r);
		//int ans=0;for(int i=inx;i<=inx2;i++)ans+=(v[i].s<=r);
		return ans;
	}
};
interval<1<<20> ds;
template<typename T>
struct lct {
	// queries are increasing
	int tl,tr;lct<T> *l,*r; T f;
	lct(){
		init();
	}
	lct(int a,int b){
		init(a,b);
	}
	// changing r changes the answer wtf
	void init(int l=0,int r=1<<20){ // increasing r makes it bigger
		tl=l;tr=r;this->l=NULL;this->r=NULL;f={INF,0ll,INF};
	}
	void add(T l){
		int tm=(tl+tr)>>1;
		if(make_pair(f.get(tm),f.b)>make_pair(l.get(tm),l.b))swap(l,f);
		if(f.get(tl)<=l.get(tl) and f.get(tr)<=l.get(tr))return;
		if(tl==tr)return;
		if(f.get(tl)>l.get(tl)){
			if(!this->l)this->l=new lct(tl,tm);
			this->l->add(f);
		}else{// if(f.get(tr)>l.get(tr)){
			if(!r)r=new lct(tm+1ll,tr);
			r->add(f);
		}
	}
	int query(int x){
		int tm=(tl+tr)>>1;
		int ans=f.get(x);
		if(tl==tr)return ans;
		if(x<=tm and l){
			ans=min(ans,l->query(x));
		}else if(r){
			ans=min(ans,r->query(x));
		}
		return ans;
	}
};
/*
template<typename T>
struct lct {
	// queries are increasing
	vector<T> v;
	void init(){
		v.clear();
	}
	void add(T l){
		v.push_back(l);
	}
	int query(int x){
		int ans=1e18;
		for(auto i:v)ans=min(ans,i.get(x));
		return ans;
	}
};*/

struct F{
	int c,m,b;
	int get(int x){
		//if(c>=INF)return c;
		//if(x<=b)return c;
		return c+m*(ds.query(b+1ll,x));
	}
	const bool operator<(F other)const {
		return b>other.b;
	}
};

priority_queue<F> ins[100005];
lct<F> cht[100005];

int 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){
	for(int i=0;i<n;i++){
		while(ins[i].size())ins[i].pop();
		cht[i].init();
	}
	ds.init();

	vector<path> paths(m);
	vector<int> cmp={-1};
	for(int i=0;i<m;i++){
		paths[i].u=_x[i];paths[i].v=_y[i];paths[i].a=_a[i];paths[i].b=_b[i];paths[i].c=_c[i];
		cmp.push_back(_a[i]);cmp.push_back(_b[i]);
	}
	for(int i=0;i<w;i++){
		cmp.push_back(l[i]);cmp.push_back(r[i]);
	}
	sort(all(cmp));cmp.resize(unique(all(cmp))-cmp.begin());
	for(int i=0;i<m;i++){
		paths[i].a=lower_bound(all(cmp),paths[i].a)-cmp.begin();
		paths[i].b=lower_bound(all(cmp),paths[i].b)-cmp.begin();
	}
	for(int i=0;i<w;i++){
		l[i]=lower_bound(all(cmp),l[i])-cmp.begin();
		r[i]=lower_bound(all(cmp),r[i])-cmp.begin();
		ds.add(l[i],r[i]);
	}
	ds.process();
	sort(all(paths),[&](path a,path b){
		return a.a<b.a;
	});
	for(int i=0;i<m;i++)paths[i].inx=i;
	// need to put a queue of paths just processed to insert ordered by b value
	cht[0].add(F{0,t[0],-1});

	for(path i:paths){
		// 1. update i.u until we get to i.a
		while(ins[i.u].size() and ins[i.u].top().b<=i.a){
			cht[i.u].add(ins[i.u].top());ins[i.u].pop();
		}
		// 2. query cht[i.u] for our i.a-1 value
		int v=cht[i.u].query(i.a-1ll)+i.c;
		v=min(INF,v);
		dbg(i.u,i.v,i.a,i.b,v);
		F ne;ne.c=v;ne.m=t[i.v];ne.b=i.b;
		// 3. insert the func that we make into 
		ins[i.v].push(ne);
	}
	while(ins[n-1].size()){
		cht[n-1].add(ins[n-1].top());ins[n-1].pop();
	}
	int ans=cht[n-1].query(1<<20);
	if(ans>=INF)ans=-1;
	return ans;

}

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