Submission #241298

#	Time	Username	Problem	Language	Result	Execution time	Memory
241298		Mercenary	Treatment Project (JOI20_treatment)	C++14	100 / 100	338 ms	33168 KiB

treatment

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 1e5 + 10;

int n , m;

struct project{
    int t , l , r , c , id;
    int t1;
}a[maxn];
ll dis[maxn];
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;

template<char T>
struct BIT{
    vector<ii> val[maxn];
    void add(int x , ii y){
        if(T){
            for( ; x > 0 ; x &= x - 1)
                val[x].pb(y);
        }else{
             for( ; x < maxn ; x += x & -x)
                val[x].pb(y);
        }
    }
    void update_dis(int u , ll d){
        d += a[u].c;
//        cout << u << " " <<  d << endl;
        if(dis[u] > d){
            dis[u] = d;
            pq.push(mp(d , u));
        }
    }
    void del(int x , int y , ll dis){
        if(T){
            for( ; x < maxn ; x += x & -x){
                while(val[x].size() > 0 && val[x].back().first <= y){
                    update_dis(val[x].back().second , dis);
                    val[x].pop_back();
                }
            }
        }else{
             for( ; x > 0 ; x &= x - 1){
                while(val[x].size() > 0 && val[x].back().first <= y){
                    update_dis(val[x].back().second , dis);
                    val[x].pop_back();
                }
             }
        }
    }
};

BIT<0> s;
BIT<1> s1;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    fill_n(dis,maxn,1e18);
    cin >> n >> m;
    vector<int> val;
    for(int i = 0 ; i < m ; ++i){
        cin >> a[i].t >> a[i].l >> a[i].r >> a[i].c;
        a[i].id = i;
        a[i].l--;
        val.pb(a[i].t);
    }
    sort(val.begin(),val.end());
    for(int i = 0 ; i < m ; ++i){
        a[i].t1 = lower_bound(val.begin(),val.end(),a[i].t) - val.begin() + 1;
    }
    sort(a , a + m , [&](const project x , const project y){
        return x.t + x.l > y.t + y.l;
         });
    for(int i = 0 ; i < m ; ++i){
        s1.add(a[i].t1,mp(a[i].t + a[i].l , a[i].id));
    }
    sort(a , a + m , [&](const project x , const project y){
        return x.l - x.t > y.l - y.t;
         });
    for(int i = 0 ; i < m ; ++i){
        s.add(a[i].t1,mp(a[i].l - a[i].t , a[i].id));
    }
    sort(a , a + m , [&](const project x , const project y){
        return x.id < y.id;
         });
    ll res = 1e18;
    for(int i = 0 ; i < m ; ++i){
        if(a[i].l == 0){
            dis[i] = a[i].c;
            pq.push(mp(dis[i] , i));
        }
    }
    while(pq.size()){
        auto u = pq.top();pq.pop();
        if(u.first != dis[u.second])continue;
        int i = u.second;
//        cout << i << endl;
        s1.del(a[i].t1 , a[i].r + a[i].t , u.first);
        s.del(a[i].t1 , a[i].r - a[i].t , u.first);
    }
    for(int i = 0 ; i < m ; ++i){
        if(a[i].r == n){
//            cout << i << " " << dis[i] << endl;
            res = min(res , dis[i]);
        }
    }
    if(res == 1e18)cout << -1;
    else cout << res;
}

Compilation message (stderr)

treatment.cpp: In function 'int main()':
treatment.cpp:75:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".INP", "r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
treatment.cpp:76:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".OUT", "w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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