Submission #247187

#	Time	Username	Problem	Language	Result	Execution time	Memory
247187		onjo0127	Treatment Project (JOI20_treatment)	C++11	35 / 100	1156 ms	524288 KiB

treatment

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
const ll INF = 1LL * 1e18;

inline int getc(vector<int> &V, int x) { return lower_bound(V.begin(), V.end(), x) - V.begin() + 1; }

ll D[100009];
deque<pii> PT[300009], QT[300009];
int T[100009], L[100009], R[100009], C[100009];
bool chk[100009];

void updP(int idx, int s, int e, int l, int r, int id) {
	if(r < s || e < l) return;
	if(l <= s && e <= r) {
		PT[idx].push_back({T[id], id});
		return;
	}
	int m = s+e >> 1;
	updP(idx*2, s, m, l, r, id);
	updP(idx*2+1, m+1, e, l, r, id);
}

void updQ(int idx, int s, int e, int l, int r, int id) {
	if(r < s || e < l) return;
	if(l <= s && e <= r) {
		QT[idx].push_back({T[id], id});
		return;
	}
	int m = s+e >> 1;
	updQ(idx*2, s, m, l, r, id);
	updQ(idx*2+1, m+1, e, l, r, id);
}

void getP(ll pc, priority_queue<pli> &pq, int idx, int s, int e, int p, int t) {
	if(p < s || e < p) return;
	while(PT[idx].size()) {
		int ti, id; tie(ti, id) = PT[idx].back();
		if(ti < t) break;
		PT[idx].pop_back();
		if(chk[id]) continue;
		chk[id] = 1;
		pq.push({-(pc + C[id]), id});
	}
	if(s == e) return;
	int m = s+e >> 1;
	getP(pc, pq, idx*2, s, m, p, t);
	getP(pc, pq, idx*2+1, m+1, e, p, t);
}

void getQ(ll pc, priority_queue<pli> &pq, int idx, int s, int e, int p, int t) {
	if(p < s || e < p) return;
	while(QT[idx].size()) {
		int ti, id; tie(ti, id) = QT[idx].front();
		if(ti > t) break;
		QT[idx].pop_front();
		if(chk[id]) continue;
		chk[id] = 1;
		pq.push({-(pc + C[id]), id});
	}
	if(s == e) return;
	int m = s+e >> 1;
	getQ(pc, pq, idx*2, s, m, p, t);
	getQ(pc, pq, idx*2+1, m+1, e, p, t);
}

int main() {
	vector<int> PV, QV;
	priority_queue<pli> pq;
	int N, M; scanf("%d%d",&N,&M);
	for(int i=1; i<=M; i++) {
		scanf("%d%d%d%d", &T[i], &L[i], &R[i], &C[i]); --L[i];
		if(L[i] == 0) {
			pq.push({-C[i], i});
			chk[i] = 1;
		}
		PV.push_back(L[i] + T[i]);
		PV.push_back(R[i] + T[i]);
		QV.push_back(L[i] - T[i]);
		QV.push_back(R[i] - T[i]);
	}
	sort(PV.begin(), PV.end()); PV.resize(unique(PV.begin(), PV.end()) - PV.begin());
	sort(QV.begin(), QV.end()); QV.resize(unique(QV.begin(), QV.end()) - QV.begin());
	int PM = PV.size(), QM = QV.size();
	for(int i=1; i<=M; i++) {
		int pl = getc(PV, L[i] + T[i]), pr = getc(PV, R[i] + T[i]);
		updP(1, 1, PM, pl, pr, i);
		int ql = getc(QV, L[i] - T[i]), qr = getc(QV, R[i] - T[i]);
		updQ(1, 1, QM, ql, qr, i);
	}
	for(int i=1; i<=4*PM; i++) sort(PT[i].begin(), PT[i].end());
	for(int i=1; i<=4*QM; i++) sort(QT[i].begin(), QT[i].end());
	memset(D, -1, sizeof(D));
	while(pq.size()) {
		ll c; int x; tie(c, x) = pq.top(); pq.pop(); c = -c;
		D[x] = c;
		getP(c, pq, 1, 1, PM, getc(PV, R[x] + T[x]), T[x]);
		getQ(c, pq, 1, 1, QM, getc(QV, R[x] - T[x]), T[x]);
	}
	ll ans = INF;
	for(int i=1; i<=M; i++) if(R[i] == N && D[i] != -1) ans = min(ans, D[i]);
	if(ans != INF) printf("%lld", ans);
	else puts("-1");
	return 0;
}

Compilation message (stderr)

treatment.cpp: In function 'void updP(int, int, int, int, int, int)':
treatment.cpp:21:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = s+e >> 1;
          ~^~
treatment.cpp: In function 'void updQ(int, int, int, int, int, int)':
treatment.cpp:32:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = s+e >> 1;
          ~^~
treatment.cpp: In function 'void getP(ll, std::priority_queue<std::pair<long long int, int> >&, int, int, int, int, int)':
treatment.cpp:48:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = s+e >> 1;
          ~^~
treatment.cpp: In function 'void getQ(ll, std::priority_queue<std::pair<long long int, int> >&, int, int, int, int, int)':
treatment.cpp:64:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = s+e >> 1;
          ~^~
treatment.cpp: In function 'int main()':
treatment.cpp:72:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int N, M; scanf("%d%d",&N,&M);
            ~~~~~^~~~~~~~~~~~~~
treatment.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &T[i], &L[i], &R[i], &C[i]); --L[i];
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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