Submission #232953

#	Time	Username	Problem	Language	Result	Execution time	Memory
232953		2fat2code	Pinball (JOI14_pinball)	C++17	100 / 100	219 ms	14580 KiB

pinball

#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 (stderr)

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 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 49 / 49