Submission #373393

#	Time	Username	Problem	Language	Result	Execution time	Memory
373393		BartolM	Pinball (JOI14_pinball)	C++17	100 / 100	320 ms	23904 KiB

pinball

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
typedef pair <pii, pii> ppp;

const int INF=0x3f3f3f3f;
const ll MAX=(ll)INF*INF;
const int N=1e5+5;
const int OFF=(1<<19);

struct Tour{
    ll T[2*OFF];
    Tour() {
        fill(T, T+2*OFF, MAX);
    }
    void update(int pos, ll x) {
        pos+=OFF; T[pos]=min(T[pos], x);
        pos/=2;
        while (pos) {
            T[pos]=min(T[pos*2], T[pos*2+1]);
            pos/=2;
        }
    }
    ll query(int a, int b, int pos=1, int lo=0, int hi=OFF) {
        if (lo>=a && hi<=b) return T[pos];
        if (lo>=b || hi<=a) return MAX;
        int mid=(lo+hi)/2;
        return min(query(a, b, pos*2, lo, mid), query(a, b, pos*2+1, mid, hi));
    }
};

int n, m;
ppp p[N];
vector <int> saz;
Tour T1, Tm;

int sazmi(int x) {
    return lower_bound(saz.begin(), saz.end(), x)-saz.begin();
}

void solve() {
    ll sol=MAX;
    T1.update(0, 0); Tm.update(m, 0);
    for (int i=0; i<n; ++i) {
        ll a1=T1.query(p[i].X.X, p[i].X.Y+1), am=Tm.query(p[i].X.X, p[i].X.Y+1);
        sol=min(sol, a1+am+p[i].Y.Y);
        T1.update(p[i].Y.X, a1+p[i].Y.Y);
        Tm.update(p[i].Y.X, am+p[i].Y.Y);
    }
    printf("%lld\n", sol>=MAX ? -1 : sol);
}

void load() {
    scanf("%d %d", &n, &m);
    for (int i=0; i<n; ++i) {
        scanf("%d %d %d %d", &p[i].X.X, &p[i].X.Y, &p[i].Y.X, &p[i].Y.Y);
        saz.pb(p[i].X.X); saz.pb(p[i].X.Y); saz.pb(p[i].Y.X);
    }
    saz.pb(1); saz.pb(m);
    sort(saz.begin(), saz.end());
    saz.erase(unique(saz.begin(), saz.end()), saz.end());
    m=sazmi(m);
    for (int i=0; i<n; ++i) {
        p[i].X.X=sazmi(p[i].X.X);
        p[i].X.Y=sazmi(p[i].X.Y);
        p[i].Y.X=sazmi(p[i].Y.X);
    }
}

int main() {
    load();
    solve();
    return 0;
}

Compilation message (stderr)

pinball.cpp: In function 'void load()':
pinball.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
pinball.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |         scanf("%d %d %d %d", &p[i].X.X, &p[i].X.Y, &p[i].Y.X, &p[i].Y.Y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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