#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;
struct BIT{
int n;
vector<int> bt;
void init(int x){
n=x;
bt.resize(n+1,1e18);
}
void update(int x,int y){
x++;
for(;x;x-=(x&-x)){
bt[x]=min(bt[x],y);
}
}
int query(int x){
x++;
int ans=1e18;
for(;x<=n;x+=(x&-x)){
ans=min(ans,bt[x]);
}
return ans;
}
};
struct qu{
int t,l,r,c;
};
vector<qu> v;
bool cmp(qu a,qu b){
return a.t<b.t;
}
bool cmp2(qu a,qu b){
return a.l<b.l;
}
signed main(){
AquA;
int n,m;
cin >> n >> m;
v.resize(m);
for(int i=0;i<m;i++){
cin >> v[i].t >> v[i].l >> v[i].r >> v[i].c;
v[i].l--;
v[i].r--;
}
sort(v.begin(),v.end(),cmp);
int nw=1;
int ans=1e18;
for(int i=0;i<m;i++){
if(i==m-1 || v[i].t!=v[i+1].t){
int uu=v[i].t-nw;
nw=v[i].t;
vector<int> gg;
for(int j=0;j<=i;j++){
if(v[i].t!=v[j].t){
v[j].l+=uu;
v[j].r-=uu;
}
if(v[j].l>v[j].r){
continue;
}
gg.push_back(v[j].l-1);
gg.push_back(v[j].r);
}
gg.push_back(0);
gg.push_back(n-1);
sort(gg.begin(),gg.end());
gg.erase(unique(gg.begin(),gg.end()),gg.end());
BIT bt;
bt.init(gg.size());
bt.update(0,0);
sort(v.begin(),v.begin()+i+1,cmp2);
for(int j=0;j<=i;j++){
//cout << v[j].t << " " << v[j].l << " " << v[j].r << "\n";
}
for(int j=0;j<=i;j++){
if(v[j].l<=v[j].r){
int a=lower_bound(gg.begin(),gg.end(),v[j].l-1)-gg.begin();
int x=bt.query(a);
int y=lower_bound(gg.begin(),gg.end(),v[j].r)-gg.begin();
bt.update(y,v[j].c+x);
//cout << i << " " << a << " " << x << " " << y << "\n";
}
}
ans=min(ans,bt.query(gg.size()-1));
}
}
cout << ans << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
5736 KB |
Output is correct |
| 2 |
Incorrect |
88 ms |
9000 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
320 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
320 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
5736 KB |
Output is correct |
| 2 |
Incorrect |
88 ms |
9000 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
