oj.uz

답안 #247147

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
247147 2020-07-11T06:48:59 Z onjo0127 치료 계획 (JOI20_treatment) C++11
5 / 100
 115 ms 29120 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[1009];
deque<pii> PT[8009], QT[8009];
int T[1009], L[1009], R[1009], C[1009];
bool chk[1009];

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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 115 ms 29120 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

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 11136 KB Output is correct
2 Correct 11 ms 11136 KB Output is correct
3 Correct 11 ms 11136 KB Output is correct
4 Correct 11 ms 11136 KB Output is correct
5 Correct 11 ms 11136 KB Output is correct
6 Correct 12 ms 11136 KB Output is correct
7 Correct 12 ms 11264 KB Output is correct
8 Correct 12 ms 11136 KB Output is correct
9 Correct 11 ms 11136 KB Output is correct
10 Correct 11 ms 11136 KB Output is correct
11 Correct 12 ms 11136 KB Output is correct
12 Correct 12 ms 11136 KB Output is correct
13 Correct 12 ms 11136 KB Output is correct
14 Correct 13 ms 11136 KB Output is correct
15 Correct 13 ms 11136 KB Output is correct
16 Correct 12 ms 11136 KB Output is correct
17 Correct 12 ms 11136 KB Output is correct
18 Correct 12 ms 11136 KB Output is correct
19 Correct 12 ms 11136 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 11136 KB Output is correct
2 Correct 11 ms 11136 KB Output is correct
3 Correct 11 ms 11136 KB Output is correct
4 Correct 11 ms 11136 KB Output is correct
5 Correct 11 ms 11136 KB Output is correct
6 Correct 12 ms 11136 KB Output is correct
7 Correct 12 ms 11264 KB Output is correct
8 Correct 12 ms 11136 KB Output is correct
9 Correct 11 ms 11136 KB Output is correct
10 Correct 11 ms 11136 KB Output is correct
11 Correct 12 ms 11136 KB Output is correct
12 Correct 12 ms 11136 KB Output is correct
13 Correct 12 ms 11136 KB Output is correct
14 Correct 13 ms 11136 KB Output is correct
15 Correct 13 ms 11136 KB Output is correct
16 Correct 12 ms 11136 KB Output is correct
17 Correct 12 ms 11136 KB Output is correct
18 Correct 12 ms 11136 KB Output is correct
19 Correct 12 ms 11136 KB Output is correct
20 Runtime error 30 ms 22912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 115 ms 29120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -