Submission #554555

#	Time	Username	Problem	Language	Result	Execution time	Memory
554555		AA_Surely	Pinball (JOI14_pinball)	C++14	100 / 100	382 ms	47328 KiB

pinball

#include <bits/stdc++.h>

#define FOR(i,x,n) 	for(int i=x; i<n; i++)
#define F0R(i,n) 	FOR(i,0,n)
#define ROF(i,x,n) 	for(int i=n-1; i>=x; i--)
#define R0F(i,n) 	ROF(i,0,n)

#define WTF 		cout << "WTF" << endl

#define IOS 		ios::sync_with_stdio(false); cin.tie(0)
#define F 			first
#define S	 		second
#define pb 			push_back

#define ALL(x) 		x.begin(), x.end()
#define RALL(x) 	x.rbegin(), x.rend()

using namespace std;
typedef long long 		LL;

typedef pair<int, int> 	PII;
typedef pair<LL, LL> 	PLL;

typedef vector<int> 	VI;
typedef vector<LL> 		VLL;
typedef vector<PII> 	VPII;
typedef vector<PLL> 	VPLL;

const int N = 1e6 + 7;
const LL INF = 5e17 + 7;

#define L 0
#define R 1

#define lc now << 1
#define rc now << 1 | 1

LL n, m;
LL tree[2][N << 2], ns[N][4];
VLL comp;

LL get(int pl, int lq, int rq, int now = 1, int ls = 0, int rs = m - 1) {
    if (rq < lq || rq < ls || rs < lq) return INF;
    if (lq <= ls && rs <= rq) return tree[pl][now];
    int mid = (ls + rs) >> 1;
    return min(get(pl, lq, rq, lc, ls, mid), get(pl, lq, rq, rc, mid + 1, rs));
}

void mnfy(int pl, int id, LL val, int now = 1, int ls = 0, int rs = m - 1) {
    if (ls == rs) {
        tree[pl][now] = min(tree[pl][now], val);
        return;
    }

    int mid = (ls + rs) >> 1;
    if (id <= mid) mnfy(pl, id, val, lc, ls, mid);
    else mnfy(pl, id, val, rc, mid + 1, rs);

    tree[pl][now] = min(tree[pl][lc], tree[pl][rc]);
    return;
}

void build(int now = 1, int ls = 0, int rs = m - 1) {
    tree[L][now] = tree[R][now] = INF;
    if (ls == rs) return;
    int mid = (ls + rs) >> 1;
    build(lc, ls, mid); build(rc, mid + 1, rs);
    return;
}

int main() {
    IOS;
    
    cin >> n >> m;
    F0R(i, n) {
        F0R(j, 3) {
            cin >> ns[i][j];
            comp.pb(ns[i][j]);
            comp.pb(max(ns[i][j] - 1, 1ll));
            comp.pb(min(ns[i][j] + 1, m));
        }
        cin >> ns[i][3];
    }

    comp.pb(1); comp.pb(n);
    sort(ALL(comp));
    comp.resize(unique(ALL(comp)) - comp.begin());
    F0R(i, n) F0R(j, 3) ns[i][j] = lower_bound(ALL(comp), ns[i][j]) - comp.begin();

    if (m == 1) {
        cout << 0 << endl;
        return 0;
    }

    /*for(int on : comp) cout << on << ' ';
    cout << endl;*/
    
    m = comp.size();
    //cout << "size = " << m << endl;
    build();
    
    mnfy(L, 0, 0);
    mnfy(R, m - 1, 0);
    
    LL ans = INF;
    F0R(i, n) {
        ans = min(ans, get(L, ns[i][0], ns[i][1]) + get(R, ns[i][0], ns[i][1]) + ns[i][3]);

        LL mn = get(L, ns[i][0], ns[i][1]);
        mnfy(L, ns[i][2], mn + ns[i][3]);

        mn = get(R, ns[i][0], ns[i][1]);
        mnfy(R, ns[i][2], mn + ns[i][3]);

        
        /*cout << "L : ";
        F0R(i, m) cout << get(L, i, i) << ' ';
        cout << endl;

        cout << "R : ";
        F0R(i, m) cout << get(R, i, i) << ' ';
        cout << endl;*/
    }

    cout << (ans < INF ? ans : -1);
}

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