답안 #65914 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
65914	2018-08-09T05:59:12 Z	reality	Pinball (JOI14_pinball)	C++17	100 / 100	523 ms	62352 KB

pinball

#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;}
#define int ll
const int N = 2e6 + 5;
const ll oo = 1e18;
int a[N];
int b[N];
int c[N];
int d[N];
ll t1[N];
ll t2[N];
void build(int l,int r,int node,ll t[]) {
    t[node] = oo;
    if (l == r)
        return ;
    int m = (l + r) / 2;
    build(l,m,node * 2,t);
    build(m+1,r,node * 2 + 1,t);
}
void update(int l,int r,int pos,ll v,int node,ll t[]) {
    if (l == r)
        return void(t[node] = min(t[node],v));
    int m = (l + r) / 2;
    if (pos <= m)
        update(l,m,pos,v,node * 2,t);
    else
        update(m+1,r,pos,v,node * 2 + 1,t);
    t[node] = min(t[node * 2],t[node * 2 + 1]);
}
ll query(int l,int r,int l1,int r1,int node,ll t[]) {
    if (l1 <= l && r <= r1)
        return t[node];
    ll ans = oo;
    int m = (l + r) / 2;
    if (l1 <= m)
        smin(ans,query(l,m,l1,r1,node * 2,t));
    if (m+1<=r1)
        smin(ans,query(m+1,r,l1,r1,node * 2 + 1,t));
    return ans;
}
int32_t main(void) {
    int n,m;
    cin>>n>>m;
    vi w;
    w.pb(1);
    w.pb(m);
    for (int i = 1;i <= n;++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();
    build(1,m,1,t1);
    build(1,m,1,t2);
    update(1,m,1,0,1,t1);
    update(1,m,m,0,1,t2);
    ll ans = oo;
    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;
    }
    for (int i = 1;i <= n;++i) {
        ll A = query(1,m,a[i],b[i],1,t1);
        ll B = query(1,m,a[i],b[i],1,t2);
        smin(ans,d[i] + A + B);
        update(1,m,c[i],A + d[i],1,t1);
        update(1,m,c[i],B + d[i],1,t2);
    }
    if (ans == oo)
        ans = -1;
    cout << ans << '\n';
    return 0;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	436 KB	Output is correct
3	Correct	2 ms	560 KB	Output is correct
4	Correct	2 ms	560 KB	Output is correct
5	Correct	2 ms	560 KB	Output is correct
6	Correct	2 ms	628 KB	Output is correct
7	Correct	2 ms	628 KB	Output is correct
8	Correct	2 ms	628 KB	Output is correct
9	Correct	4 ms	628 KB	Output is correct
10	Correct	3 ms	636 KB	Output is correct
11	Correct	2 ms	636 KB	Output is correct
12	Correct	3 ms	636 KB	Output is correct
13	Correct	3 ms	636 KB	Output is correct
14	Correct	3 ms	636 KB	Output is correct
15	Correct	3 ms	636 KB	Output is correct
16	Correct	3 ms	636 KB	Output is correct
17	Correct	8 ms	744 KB	Output is correct
18	Correct	7 ms	868 KB	Output is correct
19	Correct	6 ms	940 KB	Output is correct
20	Correct	6 ms	940 KB	Output is correct
21	Correct	4 ms	940 KB	Output is correct
22	Correct	6 ms	1068 KB	Output is correct
23	Correct	7 ms	1200 KB	Output is correct
24	Correct	6 ms	1200 KB	Output is correct

Subtask #4
49.0 / 49.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	436 KB	Output is correct
3	Correct	2 ms	560 KB	Output is correct
4	Correct	2 ms	560 KB	Output is correct
5	Correct	2 ms	560 KB	Output is correct
6	Correct	2 ms	628 KB	Output is correct
7	Correct	2 ms	628 KB	Output is correct
8	Correct	2 ms	628 KB	Output is correct
9	Correct	4 ms	628 KB	Output is correct
10	Correct	3 ms	636 KB	Output is correct
11	Correct	2 ms	636 KB	Output is correct
12	Correct	3 ms	636 KB	Output is correct
13	Correct	3 ms	636 KB	Output is correct
14	Correct	3 ms	636 KB	Output is correct
15	Correct	3 ms	636 KB	Output is correct
16	Correct	3 ms	636 KB	Output is correct
17	Correct	8 ms	744 KB	Output is correct
18	Correct	7 ms	868 KB	Output is correct
19	Correct	6 ms	940 KB	Output is correct
20	Correct	6 ms	940 KB	Output is correct
21	Correct	4 ms	940 KB	Output is correct
22	Correct	6 ms	1068 KB	Output is correct
23	Correct	7 ms	1200 KB	Output is correct
24	Correct	6 ms	1200 KB	Output is correct
25	Correct	36 ms	3032 KB	Output is correct
26	Correct	107 ms	5796 KB	Output is correct
27	Correct	409 ms	12844 KB	Output is correct
28	Correct	339 ms	15152 KB	Output is correct
29	Correct	229 ms	17456 KB	Output is correct
30	Correct	461 ms	21048 KB	Output is correct
31	Correct	484 ms	32192 KB	Output is correct
32	Correct	523 ms	32192 KB	Output is correct
33	Correct	102 ms	32192 KB	Output is correct
34	Correct	264 ms	35960 KB	Output is correct
35	Correct	433 ms	50772 KB	Output is correct
36	Correct	520 ms	54548 KB	Output is correct
37	Correct	475 ms	58316 KB	Output is correct
38	Correct	463 ms	62352 KB	Output is correct

답안 #65914

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 18.0 / 18.0

Subtask #3 22.0 / 22.0

Subtask #4 49.0 / 49.0

Subtask #1
11.0 / 11.0

Subtask #2
18.0 / 18.0

Subtask #3
22.0 / 22.0

Subtask #4
49.0 / 49.0