Submission #908780

#	Time	Username	Problem	Language	Result	Execution time	Memory
908780		tvladm2009	Pinball (JOI14_pinball)	C++17	100 / 100	174 ms	31920 KiB

pinball

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
const int N = 1e5 + 7;
const ll INF = 1e18;
int rows, cols;
 
struct kek {
    ll l;
    ll r;
    ll c;
    ll d;
};
 
kek a[N];
ll aib1[3 * N], aib2[3 * N];
ll dp1[N], dp2[N];
 
void update1(int i, ll val) {
    for (; i < 3 * N; i += i & -i) aib1[i] = min(aib1[i], val);
}
 
void update2(int i, ll val) {
    for (; i >= 1; i -= i & -i) aib2[i] = min(aib2[i], val);
}
 
ll query1(int i) {
    ll ans = INF;
    for (; i >= 1; i -= i & -i) ans = min(ans, aib1[i]);
    return ans;
}
 
ll query2(int i) {
    ll ans = INF;
    for (; i < 3 * N; i += i & -i) ans = min(ans, aib2[i]);
    return ans;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> rows >> cols;
    for (int i = 1; i <= rows; ++i) cin >> a[i].l >> a[i].r >> a[i].c >> a[i].d; 
    bool ok = 0;
    for (int i = 1; i <= rows; ++i) ok |= (a[i].l == 1);
    if (!ok) {
        cout << "-1\n";
        return 0;
    }
    ok = 0;
    for (int i = 1; i <= rows; ++i) ok |= (a[i].r == cols);
    if (!ok) {
        cout << "-1\n";
        return 0;
    }
    {
        vector<vector<int>> vals;
        for (int i = 1; i <= rows; ++i) {
            vals.push_back({a[i].l, 0, i});
            vals.push_back({a[i].r, 1, i});
            vals.push_back({a[i].c, 2, i});
        }
        sort(vals.begin(), vals.end());
        //cout << "DEBUG: " << "\n";
        //for (auto it : vals) {
            //cout << it[0] << " " << it[1] << " " << it[2] << "\n";
        //}
        int cnt = 1;
        for (int i = 0; i < vals.size(); ++i) {
            if (i > 0 && vals[i][0] != vals[i - 1][0]) ++cnt;
            auto it = vals[i];
            if (it[1] == 0) a[it[2]].l = cnt; 
            if (it[1] == 1) a[it[2]].r = cnt;
            if (it[1] == 2) a[it[2]].c = cnt;
        }
    }
    //cout << "DEBUG: " << "\n";
    //for (int i = 1; i <= rows; ++i) {
        //cout << a[i].l << " " << a[i].r << " " << a[i].c << "\n";
    //}
    ll mx = 0;
    for (int i = 1; i <= rows; ++i) {
        mx = max(mx, a[i].l);
        mx = max(mx, a[i].r);
        mx = max(mx, a[i].c);
        dp1[i] = INF;
        dp2[i] = INF;
    }
    for (int i = 1; i < 3 * N; ++i) {
        aib1[i] = INF;
        aib2[i] = INF;
    }
    for (int i = 1; i <= rows; ++i) {
        if (a[i].l == 1) dp1[i] = a[i].d;
        if (a[i].r == mx) dp2[i] = a[i].d;
    }
    //for (int i = 1; i <= rows; ++i) cout << dp1[i] << " " << dp2[i] << "\n";
    //cout << "-------\n";
    ll ans = INF;
    for (int i = 1; i <= rows; ++i) {
        //if (i == 3) {
            //cout << query2(a[i].l) << "\n"; 
        //}
        dp1[i] = min(dp1[i], query2(a[i].l) + a[i].d);
        dp2[i] = min(dp2[i], query1(a[i].r) + a[i].d);
        //cout << "UPDATAM " << a[i].c << " " << dp1[i] << "\n";
        update2(a[i].c, dp1[i]);
        update1(a[i].c, dp2[i]);
        ans = min(ans, dp1[i] + dp2[i] - a[i].d);
        //cout << dp1[i] << " " << dp2[i] << "\n";
    }
    if (ans == INF) ans = -1;
    cout << ans << endl;
    return 0;
}

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:61:34: warning: narrowing conversion of 'a[i].kek::l' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   61 |             vals.push_back({a[i].l, 0, i});
      |                             ~~~~~^
pinball.cpp:61:34: warning: narrowing conversion of 'a[i].kek::l' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
pinball.cpp:62:34: warning: narrowing conversion of 'a[i].kek::r' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   62 |             vals.push_back({a[i].r, 1, i});
      |                             ~~~~~^
pinball.cpp:62:34: warning: narrowing conversion of 'a[i].kek::r' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
pinball.cpp:63:34: warning: narrowing conversion of 'a[i].kek::c' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   63 |             vals.push_back({a[i].c, 2, i});
      |                             ~~~~~^
pinball.cpp:63:34: warning: narrowing conversion of 'a[i].kek::c' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
pinball.cpp:71:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for (int i = 0; i < vals.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~

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