oj.uz

Submission #908692

# Submission time Handle Problem Language Result Execution time Memory
908692 2024-01-16T16:50:56 Z vjudge1 Pinball (JOI14_pinball) C++17
0 / 100
 2 ms 6744 KB 
#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; 
    {
        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

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

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6744 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Incorrect 2 ms 6492 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6744 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Incorrect 2 ms 6492 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6744 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Incorrect 2 ms 6492 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6744 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Incorrect 2 ms 6492 KB Output isn't correct
8 Halted 0 ms 0 KB -