oj.uz

Submission #232953

# Submission time Handle Problem Language Result Execution time Memory
232953 2020-05-18T18:12:07 Z 2fat2code Pinball (JOI14_pinball) C++17
100 / 100
 219 ms 14580 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sz() size()
#define fr first
#define sc second
#define int long long
#define mp make_pair
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
using namespace std;

const int mmax=100005;

int m,n,ans=1e18;

struct bar{
    int l,r,mid,cost;
}arr[mmax];

vector<int>compress;
vector<pair<int,int>>aint(4*mmax);

void update(int l,int r,int pos,int val,int id,int nod){
    if(l==r){
        if(id==1) aint[nod].fr=min(aint[nod].fr,val);
        if(id==2) aint[nod].sc=min(aint[nod].sc,val);
    }
    else{
        int mid=l+(r-l)/2;
        if(pos<=mid)update(l,mid,pos,val,id,2*nod);
        else update(mid+1,r,pos,val,id,2*nod+1);
        if(id==1) aint[nod].fr=min(aint[2*nod].fr,aint[2*nod+1].fr);
        if(id==2) aint[nod].sc=min(aint[2*nod].sc,aint[2*nod+1].sc);
    }
}

int query(int l,int r,int le,int ri,int id,int nod){
    if(l>ri || r<le) return 1e18;
    else if(l>=le && r<=ri){
        if(id==1) return aint[nod].fr;
        if(id==2) return aint[nod].sc;
    }
    else{
        int mid=l+(r-l)/2;
        return min(query(l,mid,le,ri,id,2*nod),query(mid+1,r,le,ri,id,2*nod+1));
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
    srand(chrono::steady_clock::now().time_since_epoch().count());
    cin >> m >> n;
    for(int i=1;i<=m;i++){
        cin >> arr[i].l >> arr[i].r >> arr[i].mid >> arr[i].cost;
        compress.push_back(arr[i].mid);
    }
    compress.push_back(1);
    compress.push_back(n);
    sort(all(compress));
    compress.resize(unique(all(compress))-compress.begin());
    for(int i=1;i<=m;i++) arr[i].mid=lower_bound(all(compress),arr[i].mid)-compress.begin()+1;
    aint.resize(4*compress.size()+5);
    int nnew=(int)compress.size();
    for(int i=1;i<=4*nnew;i++) aint[i].fr=aint[i].sc=1e18;
    update(1,nnew,1,0,1,1);
    update(1,nnew,nnew,0,2,1);
    for(int i=1;i<=m;i++){
        int val1=0,val2=0;
        int le=lower_bound(all(compress),arr[i].l)-compress.begin()+1;
        int ri=upper_bound(all(compress),arr[i].r)-compress.begin();
        if(le<=ri){
            val1=query(1,nnew,le,ri,1,1);
            if(val1!=1e18){
                val1+=arr[i].cost;
                update(1,nnew,arr[i].mid,val1,1,1);
            }
        }
        if(le<=ri){
            val2=query(1,nnew,le,ri,2,1);
            if(val2!=1e18){
                val2+=arr[i].cost;
                update(1,nnew,arr[i].mid,val2,2,1);
            }
        }
        if(val1!=1e18 && val2!=1e18){
            ans=min(ans,val1+val2-arr[i].cost);
        }
    }
    if(ans==1e18) rc(-1);
    else rc(ans);
}

Compilation message

pinball.cpp: In function 'long long int query(long long int, long long int, long long int, long long int, long long int, long long int)':
pinball.cpp:51:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
11.0 / 11.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6656 KB Output is correct
2 Correct 8 ms 6656 KB Output is correct
3 Correct 8 ms 6656 KB Output is correct
4 Correct 8 ms 6656 KB Output is correct
5 Correct 8 ms 6656 KB Output is correct
6 Correct 8 ms 6656 KB Output is correct
7 Correct 8 ms 6656 KB Output is correct
8 Correct 8 ms 6656 KB Output is correct
9 Correct 8 ms 6656 KB Output is correct
10 Correct 8 ms 6656 KB Output is correct
11 Correct 8 ms 6656 KB Output is correct
12 Correct 8 ms 6656 KB Output is correct
13 Correct 8 ms 6656 KB Output is correct
14 Correct 8 ms 6656 KB Output is correct
15 Correct 8 ms 6656 KB Output is correct
16 Correct 8 ms 6656 KB Output is correct
17 Correct 9 ms 6784 KB Output is correct
18 Correct 10 ms 6840 KB Output is correct
19 Correct 9 ms 6784 KB Output is correct
20 Correct 9 ms 6784 KB Output is correct
21 Correct 9 ms 6656 KB Output is correct
22 Correct 9 ms 6656 KB Output is correct
23 Correct 9 ms 6656 KB Output is correct
24 Correct 9 ms 6784 KB Output is correct
25 Correct 26 ms 7552 KB Output is correct
26 Correct 57 ms 8692 KB Output is correct
27 Correct 146 ms 12276 KB Output is correct
28 Correct 151 ms 14448 KB Output is correct
29 Correct 107 ms 10620 KB Output is correct
30 Correct 185 ms 14576 KB Output is correct
31 Correct 216 ms 14580 KB Output is correct
32 Correct 212 ms 14576 KB Output is correct
33 Correct 31 ms 8192 KB Output is correct
34 Correct 94 ms 10744 KB Output is correct
35 Correct 135 ms 14576 KB Output is correct
36 Correct 219 ms 14448 KB Output is correct
37 Correct 170 ms 14576 KB Output is correct
38 Correct 171 ms 14576 KB Output is correct