oj.uz

Submission #68611

# Submission time Handle Problem Language Result Execution time Memory
68611 2018-08-17T14:24:50 Z Alexa2001 Pinball (JOI14_pinball) C++17
0 / 100
 3 ms 596 KB 
#include <bits/stdc++.h>
#define mid ((st+dr)/2)
#define left_son (node<<1)
#define right_son ((node<<1)|1)

using namespace std;

typedef long long ll;
const ll inf = 1e18;
const int Nmax = 3e5 + 5;

ll ans = inf;
int A[Nmax], B[Nmax], C[Nmax], D[Nmax];
int n, m, i;


class Aint
{
    ll a[Nmax<<2];

    public:
        void update(int node, int st, int dr, int pos, ll val)
        {
            if(st == dr)
            {
                a[node] = min(a[node], val);
                return;
            }

            if(pos <= mid) update(left_son, st, mid, pos, val);
                else update(right_son, mid+1, dr, pos, val);
            a[node] = min(a[left_son], a[right_son]);
        }

        ll query(int node, int st, int dr, int L, int R)
        {
            if(L <= st && dr <= R)
                return a[node];

            ll aux1 = inf, aux2 = inf;
            if(L <= mid) aux1 = query(left_son, st, mid, L, R);
            if(mid < R) aux2 = query(right_son, mid+1, dr, L, R);

            return min(aux1, aux2);
        }

        void build(int node, int st, int dr, int pos)
        {
            if(st == dr)
            {
                a[node] = (st == pos ? 0 : inf);
                return;
            }

            build(left_son, st, mid, pos);
            build(right_son, mid+1, dr, pos);
            a[node] = min(a[left_son], a[right_son]);
        }

} aint1, aint2;


void normalize()
{
    int i;
    map<int,int> mp;
    for(i=1; i<=n; ++i) mp[A[i]] = mp[B[i]] = mp[C[i]] = 1;

    int nr = 0;
    for(auto &it : mp) it.second = ++nr;
    for(i=1; i<=n; ++i) A[i] = mp[A[i]], B[i] = mp[B[i]], C[i] = mp[C[i]];
    m = mp.size();
}

int main()
{
  ///  freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    cin >> n >> m;

    for(i=1; i<=n; ++i)
        cin >> A[i] >> B[i] >> C[i] >> D[i];

    normalize();

    aint1.build(1, 1, m, 1);
    aint2.build(1, 1, m, m);

    for(i=1; i<=n; ++i)
    {
        ll res1 = aint1.query(1, 1, m, A[i], B[i]);
        ll res2 = aint2.query(1, 1, m, A[i], B[i]);

        ans = min(ans, res1 + res2 + D[i]);

        aint1.update( 1, 1, m, C[i], res1 + D[i] );
        aint2.update( 1, 1, m, C[i], res2 + D[i] );
    }

    cout << (ans == inf ? -1 : ans) << '\n';
    return 0;
}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 18.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 49.0

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