Submission #1034024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034024		vjudge1	Pinball (JOI14_pinball)	C++17	100 / 100	193 ms	31448 KiB

pinball

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<long long, long long>
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define lwb lower_bound
#define upb upper_bound

#define TASKNAME "NAME"

void init()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ///freopen(TASKNAME".INP","r",stdin); freopen(TASKNAME".OUT","w",stdout);
}

const int maxN = 3e5+5;
const ll INF = INT_MAX / 2, MOD = 1e9+7, INFLL = 2e18;
const double epsilon = 1e-3;

struct Device
{
    ll a,b,c,d;
    Device(ll _a = 0, ll _b = 0, ll _c = 0, ll _d = 0) : a(_a), b(_b), c(_c), d(_d) {}
};

int m, n;
Device x[maxN];
vector<int> cprs;

int pos(int k)
{
    return lwb(all(cprs),k) - cprs.begin() + 1;
}

struct SegTree
{
    ll nodes[4*maxN];

    void build(int id, int lo, int hi, int t)
    {
        if(lo == hi)
        {
            if(lo == t) nodes[id] = 0;
            else nodes[id] = INFLL;
            return;
        }
        int mid = (lo + hi) / 2;
        build(2*id, lo, mid, t);
        build(2*id+1, mid+1, hi, t);
        nodes[id] = min(nodes[2*id], nodes[2*id+1]);
    }

    void update(int id, int lo, int hi, int pos, ll val)
    {
        if(lo == hi)
        {
            nodes[id] = min(nodes[id], val);
            return;
        }
        int mid = (lo + hi) / 2;
        if(pos <= mid) update(2*id, lo, mid, pos, val);
        else update(2*id+1, mid+1, hi, pos, val);
        nodes[id] = min(nodes[2*id], nodes[2*id+1]);
    }

    ll query(int id, int lo, int hi, int u, int v)
    {
        if(lo >= u && hi <= v) return nodes[id];
        if(lo > v || hi < u) return INFLL;
        int mid = (lo + hi) / 2;
        return min(query(2*id, lo, mid, u, v), query(2*id+1, mid+1, hi, u, v));
    }
} seg1, seg2;

int main()
{
    init();
    cin >> n >> m;
    cprs.pb(1);
    cprs.pb(m);
    for(int i = 1; i <= n; i++)
    {
        ll a,b,c,d;
        cin >> a >> b >> c >> d;
        cprs.pb(a);
        cprs.pb(b);
        cprs.pb(c);
        x[i] = {a, b, c, d};
    }
    sort(all(cprs));
    unique(all(cprs));
    seg1.build(1, 1, pos(m), 1);
    seg2.build(1, 1, pos(m), pos(m));
    ll res = INFLL;
    for(int i = 1; i <= n; i++)
    {
        ll a = pos(x[i].a), b = pos(x[i].b), c = pos(x[i].c), d = x[i].d;
        ll cur1 = seg1.query(1, 1, pos(m), a, b), cur2 = seg2.query(1, 1, pos(m), a, b);
        res = min(res, cur1 + cur2 + d);
        seg1.update(1, 1, pos(m), c, cur1 + d);
        seg2.update(1, 1, pos(m), c, cur2 + d);
    }
    cout << (res == INFLL ? -1 : res);
}

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