Submission #970378

#	Time	Username	Problem	Language	Result	Execution time	Memory
970378		Beerus13	Pinball (JOI14_pinball)	C++14	0 / 100	6 ms	23128 KiB

pinball

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(), v.end()
const int N = 3e5 + 5;

int n, m;
int a[N], b[N], c[N], d[N];
vector<int> num;
ll st[2][N << 2];

void update(int u, ll val, int t) {
    int id = 1, l = 1, r = n;
    while(l < r) {
        int mid = l + r >> 1;
        if(u > mid) id = id << 1 | 1, l = mid + 1;
        else id = id << 1, r = mid;
    }
    st[t][id] = min(st[t][id], val);
    while(id > 1) id = id >> 1, st[t][id] = min(st[t][id << 1], st[t][id << 1 | 1]);
}

ll get(int u, int v, int t, int id = 1, int l = 1, int r = n) {
    if(u > r || v < l) return 1e18;
    if(u <= l && r <= v) return st[t][id];
    int mid = l + r >> 1;
    ll tmp1 = get(u, v, t, id << 1, l, mid);
    ll tmp2 = get(u, v, t, id << 1 | 1, mid + 1, r);
    return min(tmp1, tmp2);
}

void solve() {
    cin >> m >> n;
    num.push_back(1);
    num.push_back(n);
    for(int i = 1; i <= m; ++i) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        num.push_back(a[i]);
        num.push_back(b[i]);
        num.push_back(c[i]);
    }
    sort(all(num));
    num.resize(unique(all(num)) - num.begin());
    n = lower_bound(all(num), n) - num.begin() + 1;
    ll ans = 1e18;

    memset(st, 0x3f, sizeof(st));
    for(int i = 1; i <= m; ++i) {
        a[i] = lower_bound(all(num), a[i]) - num.begin() + 1;
        b[i] = lower_bound(all(num), b[i]) - num.begin() + 1;
        c[i] = lower_bound(all(num), c[i]) - num.begin() + 1;
        ll lcost = 0, rcost = 0;
        if(a[i] != 1) lcost = get(a[i], b[i], 0);
        if(b[i] != n) rcost = get(a[i], b[i], 1);
        cout << lcost << ' ' << rcost << '\n';
        ans = min(ans, lcost + rcost + d[i]);
        update(c[i], lcost + d[i], 0);
        update(c[i], rcost + d[i], 1);
    }
    cout << (ans == 1e18 ? -1 : ans) << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int test = 1;
    // cin >> test;
    while(test--) solve();
    return 0;
}

Compilation message (stderr)

pinball.cpp: In function 'void update(int, long long int, int)':
pinball.cpp:15:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 |         int mid = l + r >> 1;
      |                   ~~^~~
pinball.cpp: In function 'long long int get(int, int, int, int, int, int)':
pinball.cpp:26:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |     int mid = l + r >> 1;
      |               ~~^~~

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