#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
int T[maxn], L[maxn], R[maxn], C[maxn], p[maxn], dp[maxn];
int main(){
ios_base::sync_with_stdio(false);
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++)
cin >> T[i] >> L[i] >> R[i] >> C[i];
for (int i = 1; i <= m; i++)
p[i] = i;
sort(p+1, p+m+1, [](int a, int b){ return R[a] < R[b]; });
vector<int> S;
for (int iit = 1; iit <= m; iit++){
int 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;
}
int lo = -1, hi = S.size();
while (hi - lo > 1){
int 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);
}
int answer = -1;
for (int 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())
~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
73 ms |
4088 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
73 ms |
4088 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
