제출 #68613

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
68613		Alexa2001	Pinball (JOI14_pinball)	C++17	100 / 100	752 ms	32892 KiB

pinball

#include <bits/stdc++.h>
#define mid ((st+dr)/2)
#define left_son (node<<1)
#define right_son ((node<<1)|1)

using namespace std;

typedef long long ll;
const ll inf = 1e18;
const int Nmax = 3e5 + 5;

ll ans = inf;
int A[Nmax], B[Nmax], C[Nmax], D[Nmax];
int n, m, i;


class Aint
{
    ll a[Nmax<<2];

    public:
        void update(int node, int st, int dr, int pos, ll val)
        {
            if(st == dr)
            {
                a[node] = min(a[node], val);
                return;
            }

            if(pos <= mid) update(left_son, st, mid, pos, val);
                else update(right_son, mid+1, dr, pos, val);
            a[node] = min(a[left_son], a[right_son]);
        }

        ll query(int node, int st, int dr, int L, int R)
        {
            if(L <= st && dr <= R)
                return a[node];

            ll aux1 = inf, aux2 = inf;
            if(L <= mid) aux1 = query(left_son, st, mid, L, R);
            if(mid < R) aux2 = query(right_son, mid+1, dr, L, R);

            return min(aux1, aux2);
        }

        void build(int node, int st, int dr, int pos)
        {
            if(st == dr)
            {
                a[node] = (st == pos ? 0 : inf);
                return;
            }

            build(left_son, st, mid, pos);
            build(right_son, mid+1, dr, pos);
            a[node] = min(a[left_son], a[right_son]);
        }

} aint1, aint2;


void normalize()
{
    int i;
    map<int,int> mp;
    mp[1] = mp[m] = 1;
    for(i=1; i<=n; ++i) mp[A[i]] = mp[B[i]] = mp[C[i]] = 1;

    int nr = 0;
    for(auto &it : mp) it.second = ++nr;
    for(i=1; i<=n; ++i) A[i] = mp[A[i]], B[i] = mp[B[i]], C[i] = mp[C[i]];
    m = mp.size();
}

int main()
{
  ///  freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    cin >> n >> m;

    for(i=1; i<=n; ++i)
        cin >> A[i] >> B[i] >> C[i] >> D[i];

    normalize();

    aint1.build(1, 1, m, 1);
    aint2.build(1, 1, m, m);

    for(i=1; i<=n; ++i)
    {
        ll res1 = aint1.query(1, 1, m, A[i], B[i]);
        ll res2 = aint2.query(1, 1, m, A[i], B[i]);

        ans = min(ans, res1 + res2 + D[i]);

        aint1.update( 1, 1, m, C[i], res1 + D[i] );
        aint2.update( 1, 1, m, C[i], res2 + D[i] );
    }

    cout << (ans == inf ? -1 : ans) << '\n';
    return 0;
}

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