#include <bits/stdc++.h>
#define mp make_pair
#define F first
#define S second
#define eb emplace_back
#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())
#define printv(a, b) { \
for(auto pv : a) b << pv << " "; \
b << "\n"; \
}
using namespace std;
typedef long long ll;
using pii = pair<int, int>;
template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> a){
return o << '(' << a.F << ',' << a.S << ')';
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
map<int, ll> dp;
vector<pair<int, pii>> ev;
for(int i = 1; i <= m; i++){
int l, r, c, t;
cin >> t >> l >> r >> c;
assert(t == 1);
ev.eb(mp(l, mp(r, c)));
}
//cerr << "ok\n";
lsort(ev);
dp[0] = 0;
for(auto i : ev){
int l = i.F;
int r = i.S.F;
ll c = i.S.S;
while(!dp.empty() && dp.begin()->F < l - 1) dp.erase(dp.begin());
if(dp.empty()) break;
if(r <= dp.begin()->S) continue;
c += dp.begin()->S;
if(dp.find(r) == dp.end()) dp[r] = c;
else dp[r] = min(dp[r], c);
auto it = dp.lower_bound(r);
while(it != dp.begin() && prev(it)->S >= c){
it = dp.erase(prev(it));
}
if(next(it) != dp.end() && next(it)->S <= c) dp.erase(it);
//cerr << "test " << l << " " << r << " " << c << "\n";
//printv(dp, cerr);
}
if(dp.empty() || dp.rbegin()->F != n){
cout << "-1\n";
return 0;
}
cout << dp.rbegin()->S << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
2112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
2112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
