| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 792985 |
2023-07-25T11:59:45 Z |
bane |
Pinball (JOI14_pinball) |
C++17 |
|
1 ms |
340 KB |
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
int n, m;
struct Sparse{
vector<long long>t{(long long)1e18};
vector<long long>lazy{(long long)1e18};
vector<int>L{-1},R{-1};
inline void expand(int k){
if (L[k] == -1){
t.push_back((long long)1e18);
lazy.push_back((long long)1e18);
L[k] = (int)t.size() - 1;
}
if (R[k] == -1){
t.push_back((long long)1e18);
R[k] = (int)t.size() - 1;
lazy.push_back((long long)1e18);
}
}
inline void propagate(int k, int l, int r){
t[k] = min(t[k], lazy[k]);
if (l != r){
lazy[L[k]] = min(lazy[k], lazy[L[k]]);
lazy[R[k]] = min(lazy[R[k]], lazy[k]);
}
lazy[k] = (long long)1e18;
}
inline void range_update(int a, int b, long long cost, int l = 1, int r = n, int k = 0){
if (a > b)return;
expand(k);
propagate(k,l,r);
if (l >= a && r <= b){
lazy[k] = cost;
propagate(k,l,r);
return;
}
if (l > b || r < a)return;
int mid = (l+r) / 2;
range_update(a,b,cost,l,mid,L[k]);
range_update(a,b,cost,mid+1,r,R[k]);
}
inline long long query(int a, int l = 1, int r = n, int k = 0){
if (a < 1)return 0;
if (a > n)return 0;
expand(k);
propagate(k,l,r);
if (l == r){
return t[k];
}
int mid = (l+r) >> 1;
if (a <= mid)
return query(a,l,mid,L[k]);
else
return query(a,mid+1,r,R[k]);
}
} st, st2;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> m >> n;
long long ans = (long long)1e18;
for (int i = 0; i < m; i++){
int a,b,c,d;
cin >> a >> b >> c >> d;
//it ends here
long long CostLeft = st.query(a-1);
long long CostRight = st2.query(b+1);
ans = min(ans, CostLeft + CostRight + d);
long long CoverLeft = CostLeft + d;
long long CoverRight = CostRight + d;
st.range_update(a,c-1,CoverLeft);
st2.range_update(c+1,b, CoverRight);
}
cout << (ans == (long long)1e18 ? -1 : ans) << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
