Submission #955889

#	Time	Username	Problem	Language	Result	Execution time	Memory
955889		ZeroCool	Pinball (JOI14_pinball)	C++14	100 / 100	462 ms	57492 KiB

pinball

#include <bits/stdc++.h> 
#include <chrono> 
#include <ext/pb_ds/assoc_container.hpp> 
   
using namespace std;
using namespace __gnu_pbds;
   
template  <typename T > 
using oset = tree < T, null_type, less < T > ,  rb_tree_tag,  tree_order_statistics_node_update > ;
   
#define int long long
       
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define all(v) v.begin(),  v.end()
#define rall(v) v.rbegin(),  v.rend()
       
#define endl '\n'

using ll = long long;
using ld = long double;
       
       
#define send ios::sync_with_stdio(false);
#define help cin.tie(0);
       
void solve(int T);
       
const int N = 1e5 + 10;
const int M = 405;
const int SQRT = sqrt(N);
const int LOG = 20;
const int INF = 1e18;
const int MOD = 45678;
const ld EPS = 1e-9;
       
       
int ans;
int n,  m,  q,  l,  r,  x,  y,  mx,  mn;
       
       
int32_t main(){
    send help;
    solve(1);
}

struct SGT{

    vector<int> t;
    int n;
    SGT(int _n){n = _n;
        t.resize(4 * n, INF);
    }

    void modify(int k,int tl,int tr,int p,int v){
        if(tl == tr){
            t[k] = min(t[k],v);
            return;
        }
        int tm = (tl + tr) / 2;
        if(p <= tm)modify(k*2,tl,tm,p,v);
        else modify(k*2+1,tm+1,tr,p, v);
        t[k] = min(t[k*2], t[k*2+1]);
    }

    int query(int k,int tl,int tr,int l,int r){
        if(tr < l || r < tl)return INF;
        if(l <= tl && tr <= r)return t[k];
        int tm = (tl + tr) / 2;
        return min(query(k*2,tl,tm,l,r), query(k*2+1,tm+1,tr,l,r));
    }

    void modify(int p,int v){
        modify(1, 0, n-1,p, v);
    }
    int query(int l,int r){
        return query(1, 0,n-1,l,r);
    }
};

struct Dev{
    ll i,  a,  b,  c,  d;
    ll dp[2] = {INF,  INF};
    bool operator < (const Dev o) const {
        return b < o.b;
    }
};

Dev A[N];

void solve(int T){
    cin>>n>>m;
    set<int> s;
    for(int i = 0;i<n;i++){
        cin>>A[i].a>>A[i].b>>A[i].c>>A[i].d;
        s.insert(A[i].a);
        s.insert(A[i].b);
        s.insert(A[i].c);

        A[i].i = i;
    }
    s.insert(1);
    s.insert(m);
    
    int x = 0;

    map<int,int> mp;
    for(auto u : s)mp[u] = x++;

    for(int i = 0;i<n;i++){
        A[i].a = mp[A[i].a];
        A[i].b = mp[A[i].b];
        A[i].c = mp[A[i].c];

    }
    SGT s1(x), s2(x);

    s1.modify(0, 0);
    s2.modify(x-1,0);
    ans = INF;
    for(int i = 0;i<n;i++){
        A[i].dp[0] = s1.query(A[i].a, A[i].b) + A[i].d;
        s1.modify(A[i].c, A[i].dp[0]);
        A[i].dp[1] = s2.query(A[i].a, A[i].b) + A[i].d;
        s2.modify(A[i].c, A[i].dp[1]);
        ans = min(ans, A[i].dp[0] + A[i].dp[1] - A[i].d);
    }
    if(ans >= INF)ans = -1;
    cout<<ans<<endl;
}
//Te molam da raboti !!

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 49 / 49