oj.uz

Submission #261243

# Submission time Handle Problem Language Result Execution time Memory
261243 2020-08-11T15:17:40 Z Saboon Treatment Project (JOI20_treatment) C++14
4 / 100
 99 ms 7928 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 2e5 + 10;

ll T[maxn], L[maxn], R[maxn], C[maxn], p[maxn], dp[maxn];

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 R[a] < R[b]; });
	vector<ll> S;
	for (ll iit = 1; iit <= m; iit++){
		ll i = p[iit];
		if (L[i] == 1)
			dp[i] = C[i];
		else
			dp[i] = -1;
		if (S.empty()){
			if (dp[i] != -1)
				S.push_back(i);
			continue;
		}
		ll lo = -1, hi = S.size();
		while (hi - lo > 1){
			ll mid = (lo + hi) >> 1;
			if (R[S[mid]]+1 < L[i])
				lo = mid;
			else
				hi = mid;
		}
		if (hi == S.size())
			continue;
		if (dp[i] == -1 or dp[i] > dp[S[hi]] + C[i])
			dp[i] = dp[S[hi]] + C[i];
		while (!S.empty() and dp[S.back()] >= dp[i])
			S.pop_back();
		S.push_back(i);
	}
	ll answer = -1;
	for (ll i = 1; i <= m; i++)
		if (R[i] == n and dp[i] != -1 and (answer == -1 or answer > dp[i]))
			answer = dp[i];
	cout << answer << endl;
}

Compilation message

treatment.cpp: In function 'int main()':
treatment.cpp:37:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (hi == S.size())
       ~~~^~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 6260 KB Output is correct
2 Correct 94 ms 7928 KB Output is correct
3 Correct 84 ms 7928 KB Output is correct
4 Correct 87 ms 7928 KB Output is correct
5 Correct 77 ms 7288 KB Output is correct
6 Correct 73 ms 7256 KB Output is correct
7 Correct 79 ms 7416 KB Output is correct
8 Correct 66 ms 7288 KB Output is correct
9 Correct 69 ms 7280 KB Output is correct
10 Correct 93 ms 7292 KB Output is correct
11 Correct 75 ms 7288 KB Output is correct
12 Correct 75 ms 7288 KB Output is correct
13 Correct 93 ms 7288 KB Output is correct
14 Correct 80 ms 7288 KB Output is correct
15 Correct 85 ms 7288 KB Output is correct
16 Correct 84 ms 7288 KB Output is correct
17 Correct 76 ms 7288 KB Output is correct
18 Correct 64 ms 7288 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 416 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 416 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 6260 KB Output is correct
2 Correct 94 ms 7928 KB Output is correct
3 Correct 84 ms 7928 KB Output is correct
4 Correct 87 ms 7928 KB Output is correct
5 Correct 77 ms 7288 KB Output is correct
6 Correct 73 ms 7256 KB Output is correct
7 Correct 79 ms 7416 KB Output is correct
8 Correct 66 ms 7288 KB Output is correct
9 Correct 69 ms 7280 KB Output is correct
10 Correct 93 ms 7292 KB Output is correct
11 Correct 75 ms 7288 KB Output is correct
12 Correct 75 ms 7288 KB Output is correct
13 Correct 93 ms 7288 KB Output is correct
14 Correct 80 ms 7288 KB Output is correct
15 Correct 85 ms 7288 KB Output is correct
16 Correct 84 ms 7288 KB Output is correct
17 Correct 76 ms 7288 KB Output is correct
18 Correct 64 ms 7288 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Incorrect 1 ms 416 KB Output isn't correct
21 Halted 0 ms 0 KB -