Submission #240552

#	Time	Username	Problem	Language	Result	Execution time	Memory
240552		aggu_01000101	Pinball (JOI14_pinball)	C++14	100 / 100	245 ms	12404 KiB

pinball

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define INF 100000000000000000
#define int long long
#define lchild(i) (i*2 + 1)
#define rchild(i) (i*2 + 2)
#define mid(l, u) ((l+u)/2)
#define x(p) p.first
#define y(p) p.second
#define MOD 998244353
#define ordered_set tree<pair<int, int>, null_type,less<pair<int, int>>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
struct RR{
    int left, right, hole, cost;
};
const int M = (int)1e5 + 5;
int m, n;
int ans = INF;
int dp1[M], dp2[M];
int seg[4*M][2]; //left -> 0, right -> 1
RR arr[M];
void build(int l, int u, int i){
    seg[i][0] = seg[i][1] = INF;
    if(l==u) return;
    build(l, mid(l, u), lchild(i));
    build(mid(l, u)+1, u, rchild(i));
}
int query(int l, int u, int i, int ll, int uu, int tt){
    if(l>=ll && u<=uu) return seg[i][tt];
    if(l>uu || u<ll) return INF;
    return min(query(l, mid(l, u), lchild(i), ll, uu, tt), query(mid(l, u)+1, u, rchild(i), ll, uu, tt));
}
int update(int l, int u, int i, int ll, int up, int tt){
    if(l>=ll && u<=ll) return seg[i][tt] = min(up, seg[i][tt]);
    if(l>ll || u<ll) return seg[i][tt];
    return seg[i][tt] = min(update(l, mid(l, u), lchild(i), ll, up, tt), update(mid(l,u)+1, u, rchild(i), ll, up, tt));
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //2 3 3 4 5
    cin>>m>>n;
    vector<int> holes;
    for(int i = 0;i<m;i++){
        cin>>arr[i].left>>arr[i].right>>arr[i].hole>>arr[i].cost;
        holes.push_back(arr[i].hole);
    }
    build(0, m-1, 0);
    sort(holes.begin(), holes.end());
    for(int i = 0;i<m;i++){
        int begc = lower_bound(holes.begin(), holes.end(), arr[i].left) - holes.begin(); //index of first hole that is in the range
        int endc = (upper_bound(holes.begin(), holes.end(), arr[i].right) - holes.begin()) - 1; //index of last hole that is in the range
        int currc = lower_bound(holes.begin(), holes.end(), arr[i].hole) - holes.begin();
        //cout<<begc<<" "<<endc<<" "<<arr[i].left<<" "<<arr[i].right<<"\n";
        //Getting it here from the right
        int rightcost = (arr[i].right == n)?0:query(0, m-1, 0, begc, endc, 1);
        int leftcost = (arr[i].left==1)?0:query(0, m-1, 0, begc, endc, 0);
        //cout<<i<<" "<<leftcost<<" "<<rightcost<<" "<<arr[i].cost<<"\n";
        //calculate cost of using this as the funnel
        ans = min(ans, leftcost + rightcost + arr[i].cost);
        //update cost of going through this hole
        //right
        update(0, m-1, 0, currc, rightcost + arr[i].cost, 1);
        //left
        update(0, m-1, 0, currc, leftcost + arr[i].cost, 0);
    }
    if(ans>=INF) ans = -1;
    cout<<ans<<"\n";
}

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 49 / 49