답안 #96056 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
96056	2019-02-05T13:53:08 Z	bogdan10bos	Pinball (JOI14_pinball)	C++14	51 / 100	1000 ms	62600 KB

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

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.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	380 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	380 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct

Subtask #2
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	380 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	380 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	380 KB	Output is correct
12	Correct	3 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	3 ms	376 KB	Output is correct

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	380 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	380 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	380 KB	Output is correct
12	Correct	3 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	3 ms	376 KB	Output is correct
15	Correct	2 ms	380 KB	Output is correct
16	Correct	3 ms	504 KB	Output is correct
17	Correct	4 ms	632 KB	Output is correct
18	Correct	3 ms	380 KB	Output is correct
19	Correct	5 ms	888 KB	Output is correct
20	Correct	4 ms	632 KB	Output is correct
21	Correct	3 ms	632 KB	Output is correct
22	Correct	6 ms	888 KB	Output is correct
23	Correct	5 ms	892 KB	Output is correct
24	Correct	6 ms	1016 KB	Output is correct

Subtask #4
0 / 49.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	380 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	380 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	380 KB	Output is correct
12	Correct	3 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	3 ms	376 KB	Output is correct
15	Correct	2 ms	380 KB	Output is correct
16	Correct	3 ms	504 KB	Output is correct
17	Correct	4 ms	632 KB	Output is correct
18	Correct	3 ms	380 KB	Output is correct
19	Correct	5 ms	888 KB	Output is correct
20	Correct	4 ms	632 KB	Output is correct
21	Correct	3 ms	632 KB	Output is correct
22	Correct	6 ms	888 KB	Output is correct
23	Correct	5 ms	892 KB	Output is correct
24	Correct	6 ms	1016 KB	Output is correct
25	Correct	40 ms	3448 KB	Output is correct
26	Correct	160 ms	11208 KB	Output is correct
27	Correct	443 ms	19532 KB	Output is correct
28	Correct	165 ms	5880 KB	Output is correct
29	Correct	337 ms	18032 KB	Output is correct
30	Correct	285 ms	7908 KB	Output is correct
31	Correct	716 ms	32536 KB	Output is correct
32	Correct	635 ms	23272 KB	Output is correct
33	Correct	100 ms	12528 KB	Output is correct
34	Correct	410 ms	31436 KB	Output is correct
35	Correct	456 ms	62536 KB	Output is correct
36	Execution timed out	1052 ms	62600 KB	Time limit exceeded
37	Halted	0 ms	0 KB	-

답안 #96056

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 18.0 / 18.0

Subtask #3 22.0 / 22.0

Subtask #4 0 / 49.0

Subtask #1
11.0 / 11.0

Subtask #2
18.0 / 18.0

Subtask #3
22.0 / 22.0

Subtask #4
0 / 49.0