Submission #1279328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279328		Bui_Quoc_Cuong	Pinball (JOI14_pinball)	C++20	100 / 100	185 ms	20908 KiB

pinball

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;

int n, m;
int a[N], b[N], c[N], d[N];

namespace sub1 {
    long long dp[N][3];
    void solve () {
        vector <int> seg;
        for (int i = 1; i <= n; i++) {
            seg.push_back(i);
        }
        sort(seg.begin(), seg.end(), [&] (int i, int j) {
            return a[i] < a[j];
        });
        memset(dp, 0x3f, sizeof dp);
        for (int i = 0; i < n; i++) {
            if (a[seg[i]] == 1) {
                dp[seg[i]][0] = 0;
            }
            for (int j = 0; j < i; j++) {
                if (seg[j] < seg[i] && c[seg[j]] >= a[seg[i]] && c[seg[j]] <= b[seg[i]]) {
                    dp[seg[i]][0] = min(dp[seg[i]][0], dp[seg[j]][0]);
                }
            }
            dp[seg[i]][0]+= d[seg[i]];
        }   
        reverse(seg.begin(), seg.end());
        for (int i = 0; i < n; i++) {
            if (b[seg[i]] == m) {   
                dp[seg[i]][1] = 0;
            }
            for (int j = 0; j < i; j++) {
                if (seg[j] < seg[i] && c[seg[j]] >= a[seg[i]] && c[seg[j]] <= b[seg[i]]) {
                    dp[seg[i]][1] = min(dp[seg[i]][1], dp[seg[j]][1]);
                }
            }
            dp[seg[i]][1]+= d[seg[i]];
        }   
        long long ans = 1e18;
        for (int i = 1; i <= n; i++) {
            ans = min(ans, dp[i][0] + dp[i][1] - d[i]);
        }
        cout << (ans >= 1e18 ? - 1 : ans);
    }
}

namespace sub2 {        
    long long dp[N][3];
    int decompress[N];
    vector <int> values;
    long long st[4 * N];
    int Lim_Seg;

    void update (int pos, long long val) {
        int id = 1, l = 1, r = Lim_Seg;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (pos <= mid) id = id << 1, r = mid;
            else id = id << 1 | 1, l = mid + 1;
        }
        st[id] = min(st[id], val);
        while (id > 1) {
            id >>= 1;
            st[id] = min(st[id << 1], st[id << 1 | 1]);
        }
    }   

    long long get (int id, int l, int r, int u, int v) {
        if (l > v || r < u) return 1e18;
        if (l >= u && r <= v) return st[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 solve () { 
        for (int i = 1; i <= n; i++) {
            values.push_back(a[i]);
            values.push_back(b[i]);
            values.push_back(c[i]);
        }
        sort(values.begin(), values.end());
        for (int i = 0; i < (int)values.size(); i++) {
            decompress[i + 1] = values[i];
        }
        for (int i = 1; i <= n; i++) {
            a[i] = upper_bound(values.begin(), values.end(), a[i]) - values.begin();
            b[i] = upper_bound(values.begin(), values.end(), b[i]) - values.begin();
            c[i] = upper_bound(values.begin(), values.end(), c[i]) - values.begin();
        }
        Lim_Seg = values.size();
        memset(st, 0x3f, sizeof st);
        memset(dp, 0x3f, sizeof dp);
        for (int i = 1; i <= n; i++) {
            if (decompress[a[i]] == 1) dp[i][0] = d[i];
            dp[i][0] = min(dp[i][0], get(1, 1, Lim_Seg, a[i], b[i]) + d[i]);
            update (c[i], dp[i][0]);
        }   
        memset(st, 0x3f, sizeof st);
        for (int i = 1; i <= n; i++) {
            if (decompress[b[i]] == m) dp[i][1] = d[i];
            dp[i][1] = min(dp[i][1], get(1, 1, Lim_Seg, a[i], b[i]) + d[i]);
            update (c[i], dp[i][1]);
        }
        long long ans = 1e18;
        for (int i = 1; i <= n; i++) {
            ans = min(ans, dp[i][0] + dp[i][1] - d[i]);
        }
        cout << (ans >= 1e18 ? - 1 : ans);
    }   
}

void solve () {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }
    return sub2 :: solve();
}

signed main () {
    ios_base::sync_with_stdio(0); cin.tie(0);
    #define kieuoanh "joi14_pinball"

    if (fopen(kieuoanh".inp", "r")) {
        freopen(kieuoanh".inp", "r", stdin); freopen(kieuoanh".out", "w", stdout);
    }

    solve();

    return 0;
}

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:128:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |         freopen(kieuoanh".inp", "r", stdin); freopen(kieuoanh".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
pinball.cpp:128:53: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |         freopen(kieuoanh".inp", "r", stdin); freopen(kieuoanh".out", "w", stdout);
      |                                              ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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