oj.uz

Submission #247152

# Submission time Handle Problem Language Result Execution time Memory
247152 2020-07-11T06:52:11 Z onjo0127 Treatment Project (JOI20_treatment) C++11
5 / 100
 200 ms 127328 KB 
#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[8009], QT[80009];
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

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 200 ms 127328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 60408 KB Output is correct
2 Correct 47 ms 60408 KB Output is correct
3 Correct 58 ms 60384 KB Output is correct
4 Correct 50 ms 60408 KB Output is correct
5 Correct 49 ms 60408 KB Output is correct
6 Correct 46 ms 60408 KB Output is correct
7 Correct 64 ms 60408 KB Output is correct
8 Correct 46 ms 60408 KB Output is correct
9 Correct 48 ms 60408 KB Output is correct
10 Correct 46 ms 60408 KB Output is correct
11 Correct 47 ms 60416 KB Output is correct
12 Correct 47 ms 60408 KB Output is correct
13 Correct 49 ms 60420 KB Output is correct
14 Correct 48 ms 60416 KB Output is correct
15 Correct 57 ms 60408 KB Output is correct
16 Correct 49 ms 60416 KB Output is correct
17 Correct 47 ms 60408 KB Output is correct
18 Correct 56 ms 60408 KB Output is correct
19 Correct 47 ms 60416 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 60408 KB Output is correct
2 Correct 47 ms 60408 KB Output is correct
3 Correct 58 ms 60384 KB Output is correct
4 Correct 50 ms 60408 KB Output is correct
5 Correct 49 ms 60408 KB Output is correct
6 Correct 46 ms 60408 KB Output is correct
7 Correct 64 ms 60408 KB Output is correct
8 Correct 46 ms 60408 KB Output is correct
9 Correct 48 ms 60408 KB Output is correct
10 Correct 46 ms 60408 KB Output is correct
11 Correct 47 ms 60416 KB Output is correct
12 Correct 47 ms 60408 KB Output is correct
13 Correct 49 ms 60420 KB Output is correct
14 Correct 48 ms 60416 KB Output is correct
15 Correct 57 ms 60408 KB Output is correct
16 Correct 49 ms 60416 KB Output is correct
17 Correct 47 ms 60408 KB Output is correct
18 Correct 56 ms 60408 KB Output is correct
19 Correct 47 ms 60416 KB Output is correct
20 Runtime error 134 ms 121464 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Runtime error 200 ms 127328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -