Submission #366541

#	Time	Username	Problem	Language	Result	Execution time	Memory
366541		idk321	Pinball (JOI14_pinball)	C++11	100 / 100	739 ms	52844 KiB

pinball

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

const ll M = 1000000000000000000LL;
const int N = 300005;

ll tree[2][4 * N];

void make(ll num, int i, int a, int b, int node, int type)
{
    if (a == b)
    {
        tree[type][node] = min(tree[type][node], num);
        return;
    }

    int mid = (a + b) / 2;
    if (i <= mid) make(num, i, a, mid, node * 2, type);
    else make(num, i, mid + 1, b, node * 2 + 1, type);
    tree[type][node] = min(tree[type][node * 2], tree[type][node * 2 + 1]);
}

ll getMin(int from, int to, int a, int b, int node, int type)
{
    if (from <= a && b <= to) return tree[type][node];

    int mid = (a + b) / 2;
    ll res = M;
    if (from <= mid) res = min(res, getMin(from, to, a, mid, node * 2, type));
    if (to > mid) res = min(res, getMin(from, to, mid + 1, b, node * 2 + 1, type));

    return res;
}


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

    int m, n;
    cin >> m >> n;
    vector<array<int, 4>> devices(m);
    set<int> values;
    values.insert(1);
    values.insert(n);
    for (int i = 0; i < m; i++)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        devices[i][0] = a;
        values.insert(a);
        devices[i][1] = b;
        values.insert(b);
        values.insert(c);
        devices[i][2] = c;
        devices[i][3] = d;
    }

    map<int, int> to;
    int curTo = 1;
    for (int i : values)
    {
        to[i] = curTo;
        curTo++;
    }
    n = to[n];
    for (auto& device : devices)
    {
        for (int i = 0; i <= 2; i++) device[i] = to[device[i]];
    }



    for (int i = 0; i <= 1; i++)
    {
        for (int j = 0; j < 4 * N; j++) tree[i][j] = M;
    }

    make(0, 1, 1, n, 1, 0);
    make(0, n, 1, n, 1, 1);

    ll res = M;

    for (int i = 0; i < m; i++)
    {
        int x = devices[i][0];
        int y = devices[i][1];
        int c = devices[i][2];
        int d = devices[i][3];
        array<ll, 2> newVal;
        for (int j = 0; j < 2; j++) newVal[j] = getMin(x, y, 1, n, 1, j) + d;
        for (int j = 0; j < 2; j++ )make(newVal[j], c, 1, n, 1, j);

        res = min(res, newVal[0] + newVal[1] - d);
    }


    if (res == M) cout << -1 << "\n";
    else cout << res << "\n";
}

/*
5 6
2 4 3 5
1 2 2 8
3 6 5 2
4 6 4 7
2 4 3 10
*/

/*
6 6
2 4 3 5
1 2 2 8
3 6 5 2
4 6 4 7
2 4 3 10
1 5 1 4
*/

/*
3 5
2 4 3 10
1 3 1 20
2 5 4 30
*/

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