Submission #348250

#	Time	Username	Problem	Language	Result	Execution time	Memory
348250		nickmet2004	Treatment Project (JOI20_treatment)	C++11	0 / 100	171 ms	14052 KiB

treatment

#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
using namespace std;
const int N = 1e5 + 5 , inf = 2e9;
int n , m , T[N] , L[N], R[N] , C[N];
int a[N] , pos[N] , D[N];
vector<pair<int, int> > v;
struct Node{
    int val , v;
    Node(){}
    Node(int val , int v) : val(val) ,v(v){}
    Node operator+(const Node &A){
        if(val <= A.val) return (*this);
        else return A;
    }
}E[1<<20];
void upd(Node A , int id , int l = 0 , int r = n - 1 , int pos = 0){
    if(id < l || id > r) return;
    if(l == r){
        E[pos] = A; return;
    }
    int mid = (l + r) >> 1;
    upd(A , id , l , mid , pos * 2 + 1); upd(A ,id , mid + 1 , r ,pos * 2 + 2);
    E[pos] = E[pos * 2 + 1] + E[pos * 2 + 2];
}
Node get(int L , int R ,int l =0 , int r = n - 1,  int pos = 0){
    if(r < L || R < l) return Node(inf ,-1);
    if(L <= l && r <= R) return E[pos];
    int mid = (l + r) >> 1;
    return get(L , R , l , mid , pos * 2 + 1) + get(L , R ,mid + 1 , r , pos *2 + 2);
}

 main (){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> m >> n;
    for(int i = 0;i < n; ++i){
        cin >> T[i] >> L[i] >> R[i] >> C[i]; --L[i];
        v.emplace_back(L[i] + T[i] , i);
    }
    sort(v.begin() , v.end());
    for(int i = 0; i < n; ++i){
        int id = v[i].s;
        //cout << id << " id ";
        a[i] = L[id] - T[id];
        pos[id] = i;
        upd(Node(a[i] , id) , i);
    }//cout << endl;
    priority_queue<pair<int , int> > pq;
    for(int i = 0; i < n; ++i){
        if(L[i] == 0){
            pq.push({-C[i] , i});
            upd(Node(inf , i) , pos[i]);
        }
    }
    //cout << E[6].v << " ka " << endl;
    int ans = inf;
    while(!pq.empty()){
        auto tp = pq.top(); pq.pop();
        int i = tp.s , w= tp.f;
        //cout << w << " w "  << endl;
        if(R[i] == m) ans = min(ans , -w);
        int Y = upper_bound(v.begin() , v.end(), make_pair(R[i] + T[i] , m+1))- v.begin()-1 ;
        while(1){
            Node X = get(0 , Y);
            //cout << X.val << " " << X.v <<  " Xval " << endl;
            if(X.val <= R[i] - T[i]){
                //cout << X.v << " " << i << endl;
                pq.push({w - C[X.v] , X.v});
                upd(Node(inf , -1) , pos[X.v]);
            } else break;
        }
    }
    if(ans == inf)ans=-1;
    cout << ans;
}

Compilation message (stderr)

treatment.cpp:35:8: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   35 |  main (){
      |        ^

• Subtask 1: 0 / 4
• Subtask 2: 0 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 61