Submission #133268

#	Time	Username	Problem	Language	Result	Execution time	Memory
133268		egorlifar	Pinball (JOI14_pinball)	C++17	0 / 100	2 ms	376 KiB

pinball

/*
ЗАПУСКАЕМ
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░
 */
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>

using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; }
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left224
#define right right224
#define next next224
#define rank rank224
#define prev prev224
#define y1 y1224
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
#define mp make_pair
const string FILENAME = "input";
const int MAXN = 300228;


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

struct rmq
{
    vector<long long> d;
    int ss = 1;
    void init(int l) {
        while (ss < l) {
            ss <<= 1;
        }
        d.resize(2 * ss);
        for (int i = 0; i < 2 * ss; i++) {
            d[i] = 1e18;
        }
    }
    void upd(int i, long long val) {
        i += ss;
        chkmin(d[i], val);
        while (i >> 1 > 0) {
            i >>= 1;
            d[i] = min(d[i * 2], d[i * 2 + 1]);
        }
    }
    long long getmin(int l, int r) {
        long long res = 1e18;
        l += ss;
        r += ss;
        while (l <= r) {
            if (l & 1) {
                chkmin(res, d[l]);
                l++;
            }
            if (!(r & 1)) {
                chkmin(res, d[r]);
                r--;
            }
            l >>= 1;
            r >>= 1;
        }
        return res;
    }
};


rmq l, r;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
   // read(FILENAME);
    cin >> m >> n;
    vector<int> vx;
    vx.pb(1);
    vx.pb(n);
    for (int i = 0; i < m; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        vx.pb(a[i]);
        vx.pb(b[i]);
        vx.pb(c[i]);
    }
    sort(all(vx));
    vx.resize(distance(vx.begin(), unique(all(vx))));
    for (int i = 0; i < n; i++) {
        a[i] = lower_bound(all(vx), a[i]) - vx.begin();
         b[i] = lower_bound(all(vx), b[i]) - vx.begin();
          c[i] = lower_bound(all(vx), c[i]) - vx.begin();
    }
    l.init(sz(vx));
    r.init(sz(vx));
    l.upd(0, 0);
    r.upd(sz(vx) - 1, 0);
    long long ans = 4e18;
    for (int i = 0; i < n; i++) {
        long long f = l.getmin(a[i], b[i]);
        long long f1 = r.getmin(a[i], b[i]);
        chkmin(ans, f + f1 + d[i]);
        l.upd(c[i], f + d[i]);
        r.upd(c[i], f1 + d[i]);
    }
    cout << ans << '\n';
    return 0;
}

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