Submission #539127

#	Time	Username	Problem	Language	Result	Execution time	Memory
539127		Cross_Ratio	Pinball (JOI14_pinball)	C++14	100 / 100	245 ms	26240 KiB

pinball

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e18;
struct SegTree {
    vector<int> seg;
    int MAX;
    SegTree(int N) {
        int i;
        for(i=1;i<2*N;i*=2) {}
        seg.resize(i);
        MAX = i;
        for(i=0;i<MAX;i++) seg[i]=INF;
    }
    void update(int n) {
        n += MAX/2;
        n /= 2;
        while(n) {
            seg[n] = min(seg[2*n],seg[2*n+1]);
            n /= 2;
        }
    }
    void Edit(int n, int a) {
        seg[n+MAX/2] = min(seg[n+MAX/2],a);
        update(n);
    }
    int sum(int s, int e, int n, int ns, int ne) {
        if(e<=ns||ne<=s) return INF;
        if(s<=ns&&ne<=e) return seg[n];
        int mid = ns + ne >> 1;
        return min(sum(s,e,2*n,ns,mid),sum(s,e,2*n+1,mid,ne));
    }
    int sum(int s, int e) {
        return sum(s,e,1,0,MAX/2);
    }
};
vector<int> idx;
int id(int n) {
    return lower_bound(idx.begin(),idx.end(),n)-idx.begin();
}
int A[100005];
int B[100005];
int C[100005];
int D[100005];
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N, M;
    cin >> N >> M;
    int i, j;
    for(i=0;i<N;i++) {
        cin >> A[i] >> B[i] >> C[i] >> D[i];
        idx.push_back(A[i]);
        idx.push_back(B[i]);
        idx.push_back(C[i]);
    }
    if(M==1) {
        cout << 0;
        return 0;
    }
    idx.push_back(1);
    idx.push_back(M);
    sort(idx.begin(),idx.end());
    idx.erase(unique(idx.begin(),idx.end()),idx.end());
    SegTree tree1(idx.size()+5),tree2(idx.size()+5);
    tree1.Edit(id(1),0);
    tree2.Edit(id(M),0);
    int ans = INF;
    for(i=0;i<N;i++) {
        int l = id(A[i]);
        int r = id(B[i]);
        int po = id(C[i]);
        int c1 = tree1.sum(l, r+1);
        tree1.Edit(po,c1+D[i]);
        int c2 = tree2.sum(l, r+1);
        tree2.Edit(po,c2+D[i]);
        ans = min(ans, c1+c2+D[i]);
    }
    cout << (ans == INF ? -1 : ans);
}

Compilation message (stderr)

pinball.cpp: In member function 'long long int SegTree::sum(long long int, long long int, long long int, long long int, long long int)':
pinball.cpp:30:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
pinball.cpp: In function 'int main()':
pinball.cpp:51:12: warning: unused variable 'j' [-Wunused-variable]
   51 |     int i, j;
      |            ^

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