Submission #96057

#	Time	Username	Problem	Language	Result	Execution time	Memory
96057		bogdan10bos	Pinball (JOI14_pinball)	C++14	100 / 100	758 ms	39904 KiB

pinball

#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

typedef long long LL;

const int NMAX = 1e5;
const LL INF = 1LL << 60;

int N, M;
int st[NMAX + 5], dr[NMAX + 5], fin[NMAX + 5], cst[NMAX + 5];

class Normalizer
{
public:
    vector<int> ord;
    map<int, int> mp;

    void add(int x) { if(mp.count(x)) return; mp[x]; ord.push_back(x); }

    void normalize()
    {
        sort(begin(ord), end(ord));
        for(int i = 0; i < ord.size(); i++)
            mp[ ord[i] ] = i + 1;
    }

    int get(int x) { return mp[x]; }
}nrm;

class SegmentTree
{
public:
    int N, pos, sti, dri;
    LL val, ans;
    vector<LL> aint;

    void B(int nod, int st, int dr)
    {
        aint[nod] = INF;
        if(st == dr)    return;
        int mij = st + (dr - st) / 2;
        B(nod * 2, st, mij);
        B(nod * 2 + 1, mij + 1, dr);
    }

    void U(int nod, int st, int dr)
    {
        if(st == dr)
        {
            aint[nod] = min(aint[nod], val);
            return;
        }

        int mij = st + (dr - st) / 2;
        if(pos <= mij)  U(nod * 2, st, mij);
        else    U(nod * 2 + 1, mij + 1, dr);
        aint[nod] = min(aint[nod * 2], aint[nod * 2 + 1]);
    }

    void Q(int nod, int st, int dr)
    {
        if(sti <= st && dr <= dri)
        {
            ans = min(ans, aint[nod]);
            return;
        }

        int mij = st + (dr - st) / 2;
        if(sti <= mij)  Q(nod * 2, st, mij);
        if(mij < dri)   Q(nod * 2 + 1, mij + 1, dr);
    }

    void build(int _N)
    {
        N = _N;
        aint.resize(4 * N + 5);
        B(1, 1, N);
    }

    void update(int _pos, LL _val)
    {
        pos = _pos, val = _val;
        U(1, 1, N);
    }

    LL query(LL st, LL dr)
    {
        ans = INF;
        sti = st, dri = dr;
        Q(1, 1, N);
        return ans;
    }
}lft, rgt;

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif

    scanf("%d%d", &N, &M);
    nrm.add(1); nrm.add(M);
    for(int i = 1; i <= N; i++)
    {
        scanf("%d%d%d%d", &st[i], &dr[i], &fin[i], &cst[i]);
        nrm.add(st[i]);
        //if(st[i] > 1)   nrm.add(st[i] - 1);
        nrm.add(fin[i]);
        nrm.add(dr[i]);
        //if(dr[i] < M)   nrm.add(dr[i] + 1);
    }
    nrm.normalize();
    lft.build(nrm.ord.size());
    rgt.build(nrm.ord.size());
    lft.update(1, 0);
    rgt.update(nrm.ord.size(), 0);
    LL ans = INF;
    for(int i = 1; i <= N; i++)
    {
        st[i] = nrm.get(st[i]);
        dr[i] = nrm.get(dr[i]);

        LL l = lft.query(st[i], dr[i]);
        LL r = rgt.query(st[i], dr[i]);

        fin[i] = nrm.get(fin[i]);

        ans = min(ans, l + r + cst[i]);

        lft.update(fin[i], l + cst[i]);
        rgt.update(fin[i], r + cst[i]);
    }

    if(ans == INF)  ans = -1;
    cout << ans << '\n';


    return 0;
}

Compilation message (stderr)

pinball.cpp: In member function 'void Normalizer::normalize()':
pinball.cpp:26:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < ord.size(); i++)
                        ~~^~~~~~~~~~~~
pinball.cpp: In function 'int main()':
pinball.cpp:105:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~
pinball.cpp:109:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d", &st[i], &dr[i], &fin[i], &cst[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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