Submission #1086348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086348		underwaterkillerwhale	Pinball (JOI14_pinball)	C++17	100 / 100	160 ms	19660 KiB

pinball

#include <bits/stdc++.h>
#define se              second
#define fs              first
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N = 1e6 + 7;
const int Mod = 1e9 + 7;
const int szBL = 500;
const ll INF = 1e18;
const int BASE = 137;

int n, m, num_values;
struct Interval {
    int A, B, C, D;
}a[N];
vector<int> Nen;
ll prefix[N], suffix[N];


struct Segment_Tree {
    int Range;
    ll st[N << 2];

    void init (int n) {
        Range = n;
        rep (i, 1, n << 2) st[i] = INF;
    }

    void update (int id, int l, int r, int pos, ll val) {
        if (l > pos || r < pos) return;
        if (l == r) {
            st[id] = min(st[id], val);
            return;
        }
        int mid = l + r >> 1;
        update (id << 1, l, mid, pos, val);
        update (id << 1 | 1, mid + 1, r, pos, val);
        st[id]= min (st[id << 1], st[id << 1 | 1]);
    }

    ll get (int id, int l, int r, int u, int v) {
        if (l > v || r < u) return INF;
        if (l >= u && r <= v) return st[id];
        int mid = l + r >> 1;
        return min (get (id << 1, l, mid, u, v), get (id << 1 | 1, mid + 1, r, u, v));
    }

    void update (int pos, ll val) {
        update (1, 1, Range, pos, val);
    }
    ll get (int u, int v) {
        return get (1, 1, Range, u, v);
    }
}ST;

int CPR (int X) {
    return lower_bound(ALL(Nen), X) - Nen.begin() + 1;
}

void compress () {
    Nen = {1, m};
    rep (i, 1, n) Nen.push_back(a[i].A), Nen.push_back(a[i].B), Nen.pb(a[i].C);
    sort (ALL(Nen)); Nen.resize(unique(ALL(Nen)) - Nen.begin());
    num_values = SZ(Nen);
    rep (i, 1, n) {
        a[i].A = CPR (a[i].A), a[i].B = CPR (a[i].B), a[i].C = CPR (a[i].C);
    }
}

void solution() {
    cin >> n >> m;
    rep (i, 1, n) {
        cin >> a[i].A >> a[i].B >> a[i].C >> a[i].D;
    }
    compress();
    ST.init (num_values);
    rep (i, 1, n) {
        prefix[i] = ST.get(a[i].A, a[i].B) + a[i].D;
        if (a[i].A == 1) prefix[i] = a[i].D;
        ST.update(a[i].C, prefix[i]);
    }
    ST.init (num_values);
    rep (i, 1, n) {
        suffix[i] = ST.get(a[i].A, a[i].B) + a[i].D;
        if (a[i].B == num_values) suffix[i] = a[i].D;
        ST.update (a[i].C, suffix[i]);
    }
    ll res = INF;
    rep (i, 1, n) {
        res = min(res, prefix[i] + suffix[i] - a[i].D);
//        cout << prefix[i] <<" "<<suffix[i] <<"\n";
    }
    if (res >= INF) cout << -1 <<"\n";
    else cout << res <<"\n";


}

#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);

int main() {
//    file("c");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll num_Test = 1;
//    cin >> num_Test;
    while(num_Test--)
        solution();
}
/*
5 20
8 20 8 140
8 18 9 136
7 8 7 129
6 8 7 146
1 7 4 161
*/

Compilation message (stderr)

pinball.cpp: In member function 'void Segment_Tree::update(int, int, int, int, long long int)':
pinball.cpp:49:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |         int mid = l + r >> 1;
      |                   ~~^~~
pinball.cpp: In member function 'long long int Segment_Tree::get(int, int, int, int, int)':
pinball.cpp:58:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |         int mid = l + r >> 1;
      |                   ~~^~~

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