Submission #575022

#	Time	Username	Problem	Language	Result	Execution time	Memory
575022		MadokaMagicaFan	Pinball (JOI14_pinball)	C++14	100 / 100	469 ms	22592 KiB

pinball

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
const ll inf = 1e17;
const int md1 = 1e9+7;
const int md2 = 998244353;

#define sz(v)                       ((int)v.size())
#define pb                          push_back

#define pry                         cout << "YES\n"
#define prn                         cout << "NO\n"
#define endl                        '\n'

#define fst                         first
#define scn                         second
#define ONPC

const int N = 1e9+1;

struct d{
    int l, r;
    int out;
    ll p;
};

struct SGT{
    int n;
    vector<ll> t;

    SGT(int _n)
    {
        n = _n;
        t.assign(4 * n,inf);
    }

    void
    update(int i, int l, int r, ll x, int tg)
    {
        if (l > tg || r < tg) return;
        if (l == r) {
            t[i] = min(t[i],x);
            return;
        }
        int mid = (l+r)>>1;
        update(i<<1,l,mid,x,tg);
        update(i<<1|1,mid+1,r,x,tg);

        t[i] = min(t[i<<1],t[i<<1|1]);
        return;
    }

    ll
    query(int i, int l, int r, int tl, int tr)
    {
        if (l > tr || r < tl) return inf;
        if (l >= tl && r <= tr) return t[i];
        if (l == r) return t[i];
        int mid = (l+r)>>1;
        return min(
                query(i<<1,l,mid,tl,tr),
                query(i<<1|1,mid+1,r,tl,tr));
    }

    ll query(int l, int r) { return query(1,0,n-1,l,r); }
    void update(int tg, ll x) { update(1,0,n-1,x,tg); }

};

#ifdef ONPC
void
solve()
{
    int n, m;
    cin >> m >> n;
    vector<d> ns(m);
    set<int> tset;
    vector<int> val;
    map<int,int> comp;
    for (int i = 0; i < m; ++i) {
        cin >> ns[i].l >> ns[i].r >> ns[i].out >> ns[i].p;
        tset.insert(ns[i].out);
    }
    tset.insert(1);
    tset.insert(n);

    for (int u : tset)
        val.pb(u);

    for (int i = 0; i < sz(val); ++i) comp[val[i]]=i;

    SGT l(sz(val)+1);
    SGT r(sz(val)+1);
    l.update(comp[1],0);
    r.update(comp[n],0);

    ll ans = inf;
    for (int i = 0; i < m; ++i) {
        int lp, rp, tg;

        lp = comp[*(tset.lower_bound(ns[i].l))];
        rp = *(tset.lower_bound(ns[i].r));
        if (rp > ns[i].r)
            rp = *(--tset.lower_bound(ns[i].r));
        rp = comp[rp];
        tg = comp[*(tset.lower_bound(ns[i].out))];

        assert(lp <= rp);

        ll val1 = l.query(lp,rp);
        ll val2 = r.query(lp,rp);

        ans = min(ans,val1+val2+ns[i].p);

        l.update(tg,val1+ns[i].p);
        r.update(tg,val2+ns[i].p);
    }

    if (ans >= inf)
        cout << "-1\n";
    else
        cout << ans << endl;
}

int32_t
main(int argc, char **argv)
{
    if (argc >= 2) {
        freopen(argv[1], "r", stdin);
    } else
        ios_base::sync_with_stdio(0);cin.tie(0);
    int t = 1;
    /* cin >> t; */
    while(t--)
        solve();
}
#endif

Compilation message (stderr)

pinball.cpp: In function 'int32_t main(int, char**)':
pinball.cpp:132:7: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
  132 |     } else
      |       ^~~~
pinball.cpp:133:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
  133 |         ios_base::sync_with_stdio(0);cin.tie(0);
      |                                      ^~~
pinball.cpp:131:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |         freopen(argv[1], "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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