Submission #261374

#	Time	Username	Problem	Language	Result	Execution time	Memory
261374		Saboon	Treatment Project (JOI20_treatment)	C++14	100 / 100	2008 ms	202844 KiB

treatment

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 10;
const ll maxl = 20;

ll T[maxn], fen[maxn], L[maxn], R[maxn], C[maxn], p[maxn];
ll dp[maxn*maxl];
vector<pair<ll,ll>> g[maxn*maxl];
ll newll;

void dijkstra(ll v){
	memset(dp, -1, sizeof dp);
	set<pair<ll,ll>> s;
	dp[v] = 0;
	s.insert({dp[v], v});
	while (!s.empty()){
		v = (*s.begin()).second;
		s.erase(s.begin());
		for (auto [u, w] : g[v]){
			if (dp[u] == -1 or dp[u] > dp[v] + w){
				s.erase({dp[u],u});
				dp[u] = dp[v] + w;
				s.insert({dp[u],u});
			}
		}
	}
}

void add(ll idx, ll val){
	for (; idx < maxn; idx += idx & -idx){
		ll then = newll ++;
		if (fen[idx] != 0)
			g[then].push_back({fen[idx],0});
		fen[idx] = then;
		g[then].push_back({val,C[val]});
	}
}

void get(ll idx, ll val){
	for (; idx; idx -= idx & -idx)
		if (fen[idx] != 0)
			g[val].push_back({fen[idx],0});
}

int main(){
	ios_base::sync_with_stdio(false);
	ll n, m;
	cin >> n >> m;
	for (ll i = 1; i <= m; i++)
		cin >> T[i] >> L[i] >> R[i] >> C[i];
	for (ll i = 1; i <= m; i++)
		p[i] = i;
	sort(p+1, p+m+1, [](ll a, ll b){ return T[a] < T[b];});
	newll = m+3;
	for (ll iit = 1; iit <= m; iit++){
		ll i = p[iit];
		if (L[i] == 1)
			g[0].push_back({i,C[i]});
		if (R[i] == n)
			g[i].push_back({m+1, 0});
	}
	vector<pair<ll,ll>> event;
	for (ll iit = 1; iit <= m; iit++){
		ll i = p[iit];
		event.push_back({L[i]-T[i], -iit});
		event.push_back({R[i]-T[i]+1, +iit});
	}
	sort(event.begin(), event.end());
	for (auto [chert,iit] : event){
		if (iit < 0)
			add(-iit, p[-iit]);
		else
			get(iit, p[iit]);
	}
	event.clear();
	memset(fen, 0, sizeof fen);
	reverse(p+1, p+m+1);
	for (ll iit = 1; iit <= m; iit++){
		ll i = p[iit];
		event.push_back({L[i]+T[i], -iit});
		event.push_back({R[i]+T[i]+1, +iit});
	}
	sort(event.begin(), event.end());
	for (auto [chert,iit] : event){
		if (iit < 0)
			add(-iit, p[-iit]);
		else
			get(iit, p[iit]);
	}
	dijkstra(0);
	cout << dp[m+1] << endl;
}

Compilation message (stderr)

treatment.cpp: In function 'void dijkstra(ll)':
treatment.cpp:20:13: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
   for (auto [u, w] : g[v]){
             ^
treatment.cpp: In function 'int main()':
treatment.cpp:70:12: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
  for (auto [chert,iit] : event){
            ^
treatment.cpp:70:22: warning: unused variable 'chert' [-Wunused-variable]
  for (auto [chert,iit] : event){
                      ^
treatment.cpp:85:12: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
  for (auto [chert,iit] : event){
            ^
treatment.cpp:85:22: warning: unused variable 'chert' [-Wunused-variable]
  for (auto [chert,iit] : event){
                      ^

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