oj.uz

Submission #65850

# Submission time Handle Problem Language Result Execution time Memory
65850 2018-08-09T02:45:06 Z reality Pinball (JOI14_pinball) C++17
29 / 100
 1000 ms 5376 KB 
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class P , class Q > ostream& operator<<(ostream& stream, pair < P , Q > v){ stream << "(" << v.fi << ',' << v.se << ")"; return stream;}
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = 1e6 + 5;
int a[N];
int b[N];
int c[N];
int d[N];
int dp[4096][4096];
int main(void) {
    int n,m;
    cin>>n>>m;
    vi w;
    w.pb(1);
    w.pb(m);
    for (int i = n;i > 0;--i) {
        cin>>a[i]>>b[i]>>c[i]>>d[i];
        w.pb(a[i]);
        w.pb(b[i]);
        w.pb(c[i]);
    }
    sort(all(w));
    w.resize(unique(all(w)) - w.begin());
    m = w.size();
    for (int i = 1;i <= n;++i) {
        a[i] = lower_bound(all(w),a[i]) - w.begin() + 1;
        b[i] = lower_bound(all(w),b[i]) - w.begin() + 1;
        c[i] = lower_bound(all(w),c[i]) - w.begin() + 1;
    }
    map < pii , ll > M;
    for (int i = 1;i <= n;++i) {
        auto it = M.lower_bound(mp(c[i],-c[i]));
        vector < vector < ll > > upd;
        upd.pb({b[i],-a[i],d[i]});
        while (it != M.end()) {
            if (-it->fi.se <= c[i] && c[i] <= it->fi.fi) {
                int nl = min(-it->fi.se,a[i]);
                int nr = max(it->fi.fi,b[i]);
                upd.pb({nr,-nl,it->se + d[i]});
            }
            ++it;
        }
        for (auto it : upd) {
            if (!M.count(mp(it[0],it[1])))
                M[mp(it[0],it[1])] = it[2];
            smin(M[mp(it[0],it[1])],it[2]);
        }
    }
    if (!M.count(mp(m,-1)))
        puts("-1");
    else
        cout << M[mp(m,-1)] << '\n';
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 528 KB Output is correct
4 Correct 3 ms 648 KB Output is correct
5 Correct 3 ms 648 KB Output is correct
6 Correct 3 ms 688 KB Output is correct
7 Correct 2 ms 688 KB Output is correct
8 Correct 2 ms 688 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 528 KB Output is correct
4 Correct 3 ms 648 KB Output is correct
5 Correct 3 ms 648 KB Output is correct
6 Correct 3 ms 688 KB Output is correct
7 Correct 2 ms 688 KB Output is correct
8 Correct 2 ms 688 KB Output is correct
9 Correct 10 ms 720 KB Output is correct
10 Correct 38 ms 1012 KB Output is correct
11 Correct 50 ms 1228 KB Output is correct
12 Correct 19 ms 1248 KB Output is correct
13 Correct 28 ms 1568 KB Output is correct
14 Correct 26 ms 2260 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 528 KB Output is correct
4 Correct 3 ms 648 KB Output is correct
5 Correct 3 ms 648 KB Output is correct
6 Correct 3 ms 688 KB Output is correct
7 Correct 2 ms 688 KB Output is correct
8 Correct 2 ms 688 KB Output is correct
9 Correct 10 ms 720 KB Output is correct
10 Correct 38 ms 1012 KB Output is correct
11 Correct 50 ms 1228 KB Output is correct
12 Correct 19 ms 1248 KB Output is correct
13 Correct 28 ms 1568 KB Output is correct
14 Correct 26 ms 2260 KB Output is correct
15 Correct 6 ms 2260 KB Output is correct
16 Correct 444 ms 3156 KB Output is correct
17 Execution timed out 1075 ms 5376 KB Time limit exceeded
18 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 376 KB Output is correct
3 Correct 3 ms 528 KB Output is correct
4 Correct 3 ms 648 KB Output is correct
5 Correct 3 ms 648 KB Output is correct
6 Correct 3 ms 688 KB Output is correct
7 Correct 2 ms 688 KB Output is correct
8 Correct 2 ms 688 KB Output is correct
9 Correct 10 ms 720 KB Output is correct
10 Correct 38 ms 1012 KB Output is correct
11 Correct 50 ms 1228 KB Output is correct
12 Correct 19 ms 1248 KB Output is correct
13 Correct 28 ms 1568 KB Output is correct
14 Correct 26 ms 2260 KB Output is correct
15 Correct 6 ms 2260 KB Output is correct
16 Correct 444 ms 3156 KB Output is correct
17 Execution timed out 1075 ms 5376 KB Time limit exceeded
18 Halted 0 ms 0 KB -