oj.uz

Submission #411203

# Submission time Handle Problem Language Result Execution time Memory
411203 2021-05-24T16:32:33 Z cpp219 Pinball (JOI14_pinball) C++14
100 / 100
 353 ms 29768 KB 
#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 3e5 + 9;
const ll Log2 = 20;
const ll inf = 1e16 + 7;
typedef pair<ll,ll> LL;
vector<ll> v;
struct Seg{
    ll L,R,to,val;
};
Seg a[N];
ll m,n,L,R,to,val,st[2][4*N],ans = inf;

void upd(ll cond,ll id,ll l,ll r,ll u,ll val){
    if (u < l||r < u) return;
    if (l == r){
        st[cond][id] = min(st[cond][id],val); return;
    }
    ll mid = (l + r)/2;
    upd(cond,id*2,l,mid,u,val); upd(cond,id*2 + 1,mid + 1,r,u,val);
    st[cond][id] = min(st[cond][id*2],st[cond][id*2 + 1]);
}

ll Get(ll cond,ll id,ll l,ll r,ll u,ll v){
    if (v < l||r < u) return inf;
    if (u <= l&&r <= v) return st[cond][id];
    ll mid = (l + r)/2;
    return min(Get(cond,id*2,l,mid,u,v),Get(cond,id*2 + 1,mid + 1,r,u,v));
}

/// 0 for L    1 for R

ll Find(ll x){
    return lower_bound(v.begin(),v.end(),x) - v.begin() + 1;
}

void compress(){
    sort(v.begin(),v.end()); v.resize(unique(v.begin(),v.end()) - v.begin());
    for (ll i = 1;i <= m;i++){
        a[i].L = Find(a[i].L);
        a[i].R = Find(a[i].R); a[i].to = Find(a[i].to);
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define task "tst"
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        //freopen(task".out", "w", stdout);
    }
    for (ll i = 1;i < 4*N;i++) st[0][i] = st[1][i] = inf;
    cin>>m>>n;
    v.push_back(1); v.push_back(n);
    for (ll i = 1;i <= m;i++){
        cin>>L>>R>>to>>val; a[i] = {L,R,to,val};
        v.push_back(L); v.push_back(R); v.push_back(to);
    }
    compress(); n = v.size();
    /*
    for (ll i = 1;i <= m;i++){
        L = a[i].L; R = a[i].R; to = a[i].to; val = a[i].val;
        cout<<L<<" "<<R<<" "<<to<<" "<<val<<"\n";
    }
    cout<<n; return 0;
    */
    for (ll i = 1;i <= m;i++){
        L = a[i].L; R = a[i].R; to = a[i].to; val = a[i].val;
        ll v1 = Get(0,1,1,n,L,R),v2 = Get(1,1,1,n,L,R);
        if (L == 1) v1 = 0;
        if (R == n) v2 = 0;
        ans = min(ans,v1 + v2 + val); //cout<<v1<<" "<<v2<<" "<<val<<"\n";
        upd(0,1,1,n,to,v1 + val); upd(1,1,1,n,to,v2 + val);
    }
    if (ans != inf) cout<<ans;
    else cout<<-1;
}

Compilation message

pinball.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization "O2"
      | 
pinball.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
pinball.cpp: In function 'int main()':
pinball.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19020 KB Output is correct
2 Correct 9 ms 19020 KB Output is correct
3 Correct 9 ms 19020 KB Output is correct
4 Correct 9 ms 19052 KB Output is correct
5 Correct 9 ms 19020 KB Output is correct
6 Correct 9 ms 19020 KB Output is correct
7 Correct 9 ms 19020 KB Output is correct
8 Correct 9 ms 19040 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19020 KB Output is correct
2 Correct 9 ms 19020 KB Output is correct
3 Correct 9 ms 19020 KB Output is correct
4 Correct 9 ms 19052 KB Output is correct
5 Correct 9 ms 19020 KB Output is correct
6 Correct 9 ms 19020 KB Output is correct
7 Correct 9 ms 19020 KB Output is correct
8 Correct 9 ms 19040 KB Output is correct
9 Correct 9 ms 19020 KB Output is correct
10 Correct 9 ms 19120 KB Output is correct
11 Correct 9 ms 19116 KB Output is correct
12 Correct 9 ms 19096 KB Output is correct
13 Correct 9 ms 19072 KB Output is correct
14 Correct 10 ms 19076 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19020 KB Output is correct
2 Correct 9 ms 19020 KB Output is correct
3 Correct 9 ms 19020 KB Output is correct
4 Correct 9 ms 19052 KB Output is correct
5 Correct 9 ms 19020 KB Output is correct
6 Correct 9 ms 19020 KB Output is correct
7 Correct 9 ms 19020 KB Output is correct
8 Correct 9 ms 19040 KB Output is correct
9 Correct 9 ms 19020 KB Output is correct
10 Correct 9 ms 19120 KB Output is correct
11 Correct 9 ms 19116 KB Output is correct
12 Correct 9 ms 19096 KB Output is correct
13 Correct 9 ms 19072 KB Output is correct
14 Correct 10 ms 19076 KB Output is correct
15 Correct 9 ms 19020 KB Output is correct
16 Correct 10 ms 19124 KB Output is correct
17 Correct 11 ms 19200 KB Output is correct
18 Correct 11 ms 19148 KB Output is correct
19 Correct 12 ms 19148 KB Output is correct
20 Correct 11 ms 19124 KB Output is correct
21 Correct 11 ms 19124 KB Output is correct
22 Correct 12 ms 19248 KB Output is correct
23 Correct 11 ms 19132 KB Output is correct
24 Correct 12 ms 19132 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19020 KB Output is correct
2 Correct 9 ms 19020 KB Output is correct
3 Correct 9 ms 19020 KB Output is correct
4 Correct 9 ms 19052 KB Output is correct
5 Correct 9 ms 19020 KB Output is correct
6 Correct 9 ms 19020 KB Output is correct
7 Correct 9 ms 19020 KB Output is correct
8 Correct 9 ms 19040 KB Output is correct
9 Correct 9 ms 19020 KB Output is correct
10 Correct 9 ms 19120 KB Output is correct
11 Correct 9 ms 19116 KB Output is correct
12 Correct 9 ms 19096 KB Output is correct
13 Correct 9 ms 19072 KB Output is correct
14 Correct 10 ms 19076 KB Output is correct
15 Correct 9 ms 19020 KB Output is correct
16 Correct 10 ms 19124 KB Output is correct
17 Correct 11 ms 19200 KB Output is correct
18 Correct 11 ms 19148 KB Output is correct
19 Correct 12 ms 19148 KB Output is correct
20 Correct 11 ms 19124 KB Output is correct
21 Correct 11 ms 19124 KB Output is correct
22 Correct 12 ms 19248 KB Output is correct
23 Correct 11 ms 19132 KB Output is correct
24 Correct 12 ms 19132 KB Output is correct
25 Correct 31 ms 20028 KB Output is correct
26 Correct 74 ms 21824 KB Output is correct
27 Correct 219 ms 25536 KB Output is correct
28 Correct 176 ms 29760 KB Output is correct
29 Correct 150 ms 24480 KB Output is correct
30 Correct 235 ms 29628 KB Output is correct
31 Correct 318 ms 29592 KB Output is correct
32 Correct 298 ms 29768 KB Output is correct
33 Correct 48 ms 20920 KB Output is correct
34 Correct 153 ms 24568 KB Output is correct
35 Correct 224 ms 29624 KB Output is correct
36 Correct 353 ms 29624 KB Output is correct
37 Correct 299 ms 29604 KB Output is correct
38 Correct 288 ms 29632 KB Output is correct