oj.uz

Submission #900635

# Submission time Handle Problem Language Result Execution time Memory
900635 2024-01-08T18:02:00 Z imarn Pinball (JOI14_pinball) C++14
100 / 100
 129 ms 16988 KB 
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=3e5+5;
struct segment{
    ll a[2*N];
    void build(){
        for(int i=0;i<2*N;i++)a[i]=1e16;
    }
    void upd(int i,ll amt,int sz){
        i+=sz;a[i]=min(a[i],amt);
        for(i>>=1;i;i>>=1)a[i]=min(a[2*i],a[2*i+1]);
    }
    ll qr(int l,int r,int sz,ll res=1e16){
        for(l+=sz,r+=sz;l<r;l>>=1,r>>=1){
            if(l&1)res=min(res,a[l++]);
            if(r&1)res=min(res,a[--r]);
        }return res;
    }
}t[2];
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int m,n;cin>>m>>n;ll ans=1e15;
    vector<int> com;com.pb(1);com.pb(n);
    int a[m],b[m],c[m];ll d[m];
    for(int i=0;i<m;i++)cin>>a[i]>>b[i]>>c[i]>>d[i],com.pb(a[i]),com.pb(b[i]),com.pb(c[i]);
    sort(all(com));com.erase(unique(all(com)),com.end());t[0].build();t[1].build();int sz=com.size();
    for(int i=0;i<m;i++){
        int ax=lower_bound(all(com),a[i])-com.begin();
        int bx=lower_bound(all(com),b[i])-com.begin();
        int cx=lower_bound(all(com),c[i])-com.begin();
        ll resl=1e15,resr=1e15;
        if(a[i]==1)resl=0;
        if(b[i]==n)resr=0;
        resl=min(resl,t[0].qr(ax,bx+1,sz));
        resr=min(resr,t[1].qr(ax,bx+1,sz));
        ans=min(ans,resl+resr+d[i]);
        t[0].upd(cx,resl+d[i],sz);t[1].upd(cx,resr+d[i],sz);
    }cout<<(ans==1e15?-1:ans);
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9816 KB Output is correct
2 Correct 2 ms 9816 KB Output is correct
3 Correct 2 ms 9816 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9816 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 3 ms 9820 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9816 KB Output is correct
2 Correct 2 ms 9816 KB Output is correct
3 Correct 2 ms 9816 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9816 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 3 ms 9820 KB Output is correct
9 Correct 2 ms 9820 KB Output is correct
10 Correct 2 ms 9820 KB Output is correct
11 Correct 2 ms 9820 KB Output is correct
12 Correct 3 ms 9820 KB Output is correct
13 Correct 2 ms 9820 KB Output is correct
14 Correct 2 ms 9816 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9816 KB Output is correct
2 Correct 2 ms 9816 KB Output is correct
3 Correct 2 ms 9816 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9816 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 3 ms 9820 KB Output is correct
9 Correct 2 ms 9820 KB Output is correct
10 Correct 2 ms 9820 KB Output is correct
11 Correct 2 ms 9820 KB Output is correct
12 Correct 3 ms 9820 KB Output is correct
13 Correct 2 ms 9820 KB Output is correct
14 Correct 2 ms 9816 KB Output is correct
15 Correct 2 ms 9820 KB Output is correct
16 Correct 2 ms 9820 KB Output is correct
17 Correct 3 ms 9820 KB Output is correct
18 Correct 3 ms 9688 KB Output is correct
19 Correct 3 ms 9820 KB Output is correct
20 Correct 3 ms 9820 KB Output is correct
21 Correct 2 ms 9820 KB Output is correct
22 Correct 3 ms 9748 KB Output is correct
23 Correct 3 ms 9820 KB Output is correct
24 Correct 3 ms 9820 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9816 KB Output is correct
2 Correct 2 ms 9816 KB Output is correct
3 Correct 2 ms 9816 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9816 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 3 ms 9820 KB Output is correct
9 Correct 2 ms 9820 KB Output is correct
10 Correct 2 ms 9820 KB Output is correct
11 Correct 2 ms 9820 KB Output is correct
12 Correct 3 ms 9820 KB Output is correct
13 Correct 2 ms 9820 KB Output is correct
14 Correct 2 ms 9816 KB Output is correct
15 Correct 2 ms 9820 KB Output is correct
16 Correct 2 ms 9820 KB Output is correct
17 Correct 3 ms 9820 KB Output is correct
18 Correct 3 ms 9688 KB Output is correct
19 Correct 3 ms 9820 KB Output is correct
20 Correct 3 ms 9820 KB Output is correct
21 Correct 2 ms 9820 KB Output is correct
22 Correct 3 ms 9748 KB Output is correct
23 Correct 3 ms 9820 KB Output is correct
24 Correct 3 ms 9820 KB Output is correct
25 Correct 12 ms 10468 KB Output is correct
26 Correct 29 ms 11484 KB Output is correct
27 Correct 84 ms 14500 KB Output is correct
28 Correct 84 ms 16840 KB Output is correct
29 Correct 61 ms 13296 KB Output is correct
30 Correct 101 ms 16844 KB Output is correct
31 Correct 129 ms 16988 KB Output is correct
32 Correct 120 ms 16928 KB Output is correct
33 Correct 16 ms 11228 KB Output is correct
34 Correct 58 ms 13216 KB Output is correct
35 Correct 82 ms 16844 KB Output is correct
36 Correct 127 ms 16716 KB Output is correct
37 Correct 109 ms 16840 KB Output is correct
38 Correct 107 ms 16968 KB Output is correct