| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 564273 |
2022-05-18T19:50:20 Z |
urosk |
Pinball (JOI14_pinball) |
C++14 |
|
4 ms |
6612 KB |
// __builtin_popcount(x)
// __builtin_popcountll(x)
#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
using namespace std;
#define maxn 200005
ll n,m;
ll l[maxn],r[maxn],c[maxn],val[maxn];
ll t[4*maxn];
void upd(ll v,ll tl,ll tr,ll i,ll x){
if(tl==tr){
t[v] = x;
return;
}
ll mid = (tl+tr)/2;
if(i<=mid) upd(2*v,tl,mid,i,x);
else upd(2*v+1,mid+1,tr,i,x);
t[v] = min(t[2*v],t[2*v+1]);
}
ll get(ll v,ll tl,ll tr,ll l,ll r){
if(l>r) return llinf;
if(tl==l&&tr==r) return t[v];
ll mid = (tl+tr)/2;
return min(get(2*v,tl,mid,l,min(mid,r)),get(2*v+1,mid+1,tr,max(mid+1,l),r));
}
ll it = 1;
map<ll,ll> mp;
ll dp[maxn][2];
int main(){
ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
cin >> n >> m;
set<ll> s;
s.insert(1);
s.insert(m);
for(ll i = 1;i<=n;i++){
cin >> l[i] >> r[i] >> c[i] >> val[i];
s.insert(l[i]);
s.insert(r[i]);
s.insert(c[i]);
}
for(ll x : s) mp[x] = it++;
m = mp[m];
for(ll i = 1;i<=n;i++){
l[i] = mp[l[i]];
r[i] = mp[r[i]];
c[i] = mp[c[i]];
}
vector<ll> w = {1,m};
for(ll ii = 0;ii<2;ii++){
fill(t,t+4*maxn,llinf);
upd(1,1,it+1,w[ii],0);
for(ll i = 1;i<=n;i++){
dp[i][ii] = get(1,1,it+1,l[i],r[i]);
upd(1,1,it+1,c[i],dp[i][ii] + val[i]);
}
}
ll ans = llinf;
for(ll i = 1;i<=n;i++) ans = min(ans,dp[i][0] + dp[i][1] + val[i]);
if(ans==llinf) ans = -1;
cout<<ans<<endl;
return 0;
}
/*
5 6
2 4 3 5
1 2 2 8
3 6 5 2
4 6 4 7
2 4 3 10
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
6612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
6612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
6612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
6612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
