Submission #1178469

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178469		vnedu	Pinball (JOI14_pinball)	C++20	29 / 100	9 ms	328 KiB

pinball

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

template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }

#define fi first
#define se second

#define pb push_back
#define ii pair<int, int>

#define all(x) x.begin(), x.end()

#define TASK "nonsense"

/// end of template ///

const int ROW = 1e5 + 15;
const int COL = ROW * 3;
int numRow,numCol;
struct node
{
    int l,x,r,c;
    node() {}
    void input()
    {
        cin>>l>>r>>x>>c;
    }
} a[ROW];
namespace sub1
{
    bool check()
    {
        return (numRow<=10 && numCol<=1000);
    }
    void solve()
    {
        ll ans=LLONG_MAX;
        for (int mask=0; mask<(1<<numRow); ++mask)
        {
            bool ok=1;
            int lst=-1;
            for (int tri=1; tri<=numCol; ++tri)
            {
                int pos=tri;
                for (int k=2; k<=numRow+1; ++k)
                {
                    if (((mask>>(k-2))&1) && a[k-1].l<=pos && pos<=a[k-1].r) pos=a[k-1].x;
                }
                if (tri==1) lst=pos;
                else if (lst!=pos)
                {
                    ok=0;
                    break;
                }
            }
            if (ok)
            {
                ll sum=0;
                for (int j=0; j<numRow; ++j) if ((mask>>j)&1) sum+=a[j+1].c;
                minimize(ans,sum);
            }
        }
        cout<<(ans==LLONG_MAX?-1:ans);
    }
}
namespace subfull
{
    const ll inf = 1e18;
    vector<int> v;
    ll dp[2][ROW],t[COL<<2];
    void build(int id, int l, int r)
    {
        t[id]=inf;
        if (l==r) return;
        int mid((l+r)>>1);
        build(id<<1,l,mid);
        build(id<<1|1,mid+1,r);
    }
    void update(int id, int l, int r, int x, ll val)
    {
        if (x>r||x<l) return;
        if (l==r)
        {
            minimize(t[id],val);
            return;
        }
        int mid((l+r)>>1);
        update(id<<1,l,mid,x,val);
        update(id<<1|1,mid+1,r,x,val);
        t[id]=min(t[id<<1],t[id<<1|1]);
    }
    ll get(int id, int l, int r, int u, int v)
    {
        if (l>v||r<u) return inf;
        if (u<=l && r<=v) return t[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 work(bool state, int xxx)
    {
        build(1,1,numCol);
        for (int i=1; i<=numRow; ++i)
        {
            node &cm=a[i];
            ll cost=get(1,1,numCol,cm.l,cm.r);
            if (cm.l<=xxx && xxx<=cm.r) cost=0;
            cost=min(inf,cost+cm.c);
            dp[state][i]=cost;
            update(1,1,numCol,cm.x,cost);
        }
    }
    void solve()
    {
        for (int i=1; i<=numRow; ++i)
        {
            v.pb(a[i].l);
            v.pb(a[i].x);
            v.pb(a[i].r);
        }
        sort(all(v)); v.erase(unique(all(v)),v.end());
        for (int i=1; i<=numRow; ++i)
        {
            a[i].l=lower_bound(all(v),a[i].l)-v.begin()+1;
            a[i].x=lower_bound(all(v),a[i].x)-v.begin()+1;
            a[i].r=lower_bound(all(v),a[i].r)-v.begin()+1;
        }
        numCol=(int)v.size();
        work(0,1);
        work(1,numCol);
        ll ans=inf;
        for (int i=1; i<=numRow; ++i) minimize(ans,dp[0][i]+dp[1][i]-a[i].c);
        cout<<(ans==inf?-1:ans);
    }
}

void solve()
{
    cin>>numRow>>numCol;
    for (int i=1; i<=numRow; ++i) a[i].input();
    if (sub1::check()) return void(sub1::solve());
    return void(subfull::solve());
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);

    int testcase=1;
//    cin>>testcase;

    while (testcase--)
        solve();

//    #define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
//    cerr << "Time elapsed: " << TIME << " s.\n";
    return 0;
}

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