#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long lint;
struct sti{int s,e,d,x;}a[100005];
vector<int> v;
lint dpl[300005], dpu[300005];
vector<lint> dp_low[300005], dp_high[300005];
struct rmq{
lint tree[1050000];
int lim;
void init(int n){
memset(tree,0x3f,sizeof(tree));
for(lim = 1; lim <= n; lim <<= 1);
}
void add(int x, int v){
x += lim;
tree[x] = v;
while(x > 1){
x >>= 1;
tree[x] = min(tree[2*x],tree[2*x+1]);
}
}
lint query(int s, int e){
s += lim;
e += lim;
lint r = 1e18;
while(s < e){
if(s%2 == 1) r = max(r,tree[s++]);
if(e%2 == 0) r = max(r,tree[e--]);
s >>= 1;
e >>= 1;
}
if(s == e) r = max(r,tree[s]);
return r;
}
}rmq;
int n,m;
void input(){
scanf("%d %d",&n,&m);
v.push_back(1);
v.push_back(m);
for (int i=2; i<=n+1; i++) {
scanf("%d %d %d %d",&a[i].s,&a[i].e,&a[i].d,&a[i].x);
v.push_back(a[i].s);
v.push_back(a[i].e);
v.push_back(a[i].d);
}
sort(v.begin(),v.end());
v.resize(unique(v.begin(),v.end()) - v.begin());
for (int i=2; i<=n+1; i++) {
a[i].s = (int)(lower_bound(v.begin(),v.end(),a[i].s) - v.begin());
a[i].e = (int)(lower_bound(v.begin(),v.end(),a[i].e) - v.begin());
a[i].d = (int)(lower_bound(v.begin(),v.end(),a[i].d) - v.begin());
}
a[1] = {0,0,0,0};
a[0] = {(int)v.size()-1,(int)v.size()-1,(int)v.size()-1,0};
}
int main(){
input();
for (int i=1; i<n+2; i++) {
dpu[i] = 1e18;
for (int j=0; j<i; j++) {
if(a[j].d <= a[i].e){
dpu[i] = min(dpu[i],dpu[j]);
}
}
dpu[i] += a[i].x;
}
for (int i=n+1; i>=0; i--) {
dpl[i] = 1e18;
for (int j=i+1; j<n+2; j++) {
if(a[j].s <= a[i].d && a[i].d <= a[j].e){
dpl[i] = min(dpl[i],dpl[j]);
}
}
dpl[i] += a[i].x;
dpl[i] = min(dpl[i],dpu[i]);
}
if(dpl[1] >= 1e18) puts("-1");
else printf("%lld",dpl[1]);
}
Compilation message
pinball.cpp: In member function ‘void rmq::init(int)’:
pinball.cpp:18:38: error: ‘memset’ was not declared in this scope
memset(tree,0x3f,sizeof(tree));
^
pinball.cpp: In function ‘void input()’:
pinball.cpp:47:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&m);
^
pinball.cpp:51:61: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d",&a[i].s,&a[i].e,&a[i].d,&a[i].x);
^
