제출 #1309654

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309654		herominhsteve	Fuel Station (NOI20_fuelstation)	C++20	100 / 100	404 ms	41548 KiB

FuelStation

#include <bits/stdc++.h>
#define el '\n'
#define FNAME "ffuel"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9 + 7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}

void setup(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    if (fopen(FNAME".inp","r")){
        freopen(FNAME".inp","r",stdin);
        freopen(FNAME".out","w",stdout);
    }
}

const int INF = 1e9 + 15092007;

struct Station{
    int pos,refill,thres;
    Station(int p,int a,int b):pos(p),refill(a),thres(b) {}
    bool operator < (const Station &other) const{
        if (pos == other.pos) 
            return (refill < other.refill or (refill==other.refill and thres < other.thres));
        return pos < other.pos;
    }
    inline void unpack(int &p,int &a,int &b) const{
        p = pos;
        a = refill;
        b = thres;
    }
};

struct SegmentTree{
    struct Node{
        long long deltaSum,minPref;
        Node():deltaSum(0),minPref(0) {}
        Node(long long s,long long p):deltaSum(s),minPref(p) {}

        static Node merge(const Node &A,const Node &B){
            return Node(A.deltaSum + B.deltaSum,min(A.minPref,A.deltaSum + B.minPref));
        }

    };
    
    int n;
    vector<Node> st;

    SegmentTree(int N):n(N){
        st.resize(4 * n + 4);
    }

    void update(int node,int l,int r,int pos,long long val){
        if (l == r){
            st[node] = Node(val,val);
            return;
        }
        int mid = (l+r)>>1;
        if (pos <= mid) update(2 * node,l,mid,pos,val);
        else update(2 * node + 1,mid+1,r,pos,val);
        st[node] = Node::merge(st[2*node],st[2*node+1]);
    }

    void update(int pos,long long val){
        update(1,1,n,pos,val);
    }

    inline long long getMin(){
        return st[1].minPref;
    }

};

int n,D;
vector<Station> station;
vector<int> Pos,Refill,Threshold;

void init(){
    cin>>n>>D;
    for (int i=0;i<n;i++){
        int p,a,b; cin>>p>>a>>b;
        station.emplace_back(p,a,b);
    }
    sort(allof(station));
    Pos.assign(n + 2, 0);
    Refill.assign(n + 2, 0);
    Threshold.assign(n + 2, INF);
    for (int i = 0; i < n; i++) 
        station[i].unpack(Pos[i+1],Refill[i+1],Threshold[i+1]);
    Pos[n + 1] = D;
}

void sol(){
    SegmentTree st(n + 2);
    st.update(n+1,-D);

    set<int> processing;
    processing.insert(0); processing.insert(n+1);

    vector<int> order(n); iota(allof(order),1);
    sort(allof(order),[&](int i,int j){
        return Threshold[i] > Threshold[j];
    });

    long long res = D;
    for (int l = 0; l < n; ){
        int r = l;
        while (r + 1 < n and Threshold[order[l]] == Threshold[order[r+1]]) r++;

        for (int i = l; i <= r; i++){
            int p = order[i];
            processing.insert(p);

            set<int>::iterator it = processing.find(p);
            set<int>::iterator prv = prev(it), nxt = next(it);

            st.update(p, Refill[*prv] - (Pos[p] - Pos[*prv]));
            st.update(*nxt, Refill[p] - (Pos[*nxt] - Pos[p]));
        }

        if (st.getMin() + Threshold[order[l]] >= 0) minimize(res,-st.getMin());
        l = r + 1;
    }
    cout<<res;
}

int main(){
    setup();
    init();
    sol();
}

컴파일 시 표준 에러 (stderr) 메시지

FuelStation.cpp: In function 'void setup()':
FuelStation.cpp:16:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         freopen(FNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
FuelStation.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen(FNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 12 / 12
• Subtask 5: 19 / 19
• Subtask 6: 11 / 11
• Subtask 7: 21 / 21