Submission #676888

#	Time	Username	Problem	Language	Result	Execution time	Memory
676888		alvingogo	Treatment Project (JOI20_treatment)	C++14	0 / 100	88 ms	9000 KiB

treatment

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;

struct BIT{
	int n;
	vector<int> bt;
	void init(int x){
		n=x;
		bt.resize(n+1,1e18);
	}
	void update(int x,int y){
		x++;
		for(;x;x-=(x&-x)){
			bt[x]=min(bt[x],y);
		}
	}
	int query(int x){
		x++;
		int ans=1e18;
		for(;x<=n;x+=(x&-x)){
			ans=min(ans,bt[x]);
		}
		return ans;
	}
};
struct qu{
	int t,l,r,c;
};
vector<qu> v;
bool cmp(qu a,qu b){
	return a.t<b.t;
}
bool cmp2(qu a,qu b){
	return a.l<b.l;
}
signed main(){
    AquA;
	int n,m;
	cin >> n >> m;
	v.resize(m);
	for(int i=0;i<m;i++){
		cin >> v[i].t >> v[i].l >> v[i].r >> v[i].c;
		v[i].l--;
		v[i].r--;
	}
	sort(v.begin(),v.end(),cmp);
	int nw=1;
	int ans=1e18;
	for(int i=0;i<m;i++){
		if(i==m-1 || v[i].t!=v[i+1].t){
			int uu=v[i].t-nw;
			nw=v[i].t;
			vector<int> gg;
			for(int j=0;j<=i;j++){
				if(v[i].t!=v[j].t){
					v[j].l+=uu;
					v[j].r-=uu;
				}
				if(v[j].l>v[j].r){
					continue;
				}
				gg.push_back(v[j].l-1);
				gg.push_back(v[j].r);
			}	
			gg.push_back(0);
			gg.push_back(n-1);
			sort(gg.begin(),gg.end());
			gg.erase(unique(gg.begin(),gg.end()),gg.end());
			BIT bt;
			bt.init(gg.size());
			bt.update(0,0);
			sort(v.begin(),v.begin()+i+1,cmp2);
			for(int j=0;j<=i;j++){
				//cout << v[j].t << " " << v[j].l << " " << v[j].r << "\n";
			}
			for(int j=0;j<=i;j++){
				if(v[j].l<=v[j].r){
					int a=lower_bound(gg.begin(),gg.end(),v[j].l-1)-gg.begin();
					int x=bt.query(a);
					int y=lower_bound(gg.begin(),gg.end(),v[j].r)-gg.begin();
					bt.update(y,v[j].c+x);
					//cout << i << " " << a << " " << x << " " << y << "\n";
				} 	
			}
			ans=min(ans,bt.query(gg.size()-1));
		}
	}
	cout << ans << "\n";
    return 0;
}

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