제출 #737475

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
737475		Ronin13	Fuel Station (NOI20_fuelstation)	C++14	100 / 100	1123 ms	740048 KiB

FuelStation

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 10000001;
vector <ll> bit(nmax);

const ll mod = 1e9 + 7;

int lsb(int x){
    return x & -x;
}

void add(int pos, ll v, int n){
    while(pos <= n){
        bit[pos] += v;
        pos += lsb(pos);
    }
}

ll get(int pos){
    ll res = 0;
    while(pos){
        res += bit[pos];
        pos -= lsb(pos);
    }
    return res;
}

vector <ll> t(4 * nmax), lazy(4 * nmax);

void push(int v){
    t[2 * v] += lazy[v];
    lazy[2 * v] += lazy[v];
    t[2 * v + 1] += lazy[v];
    lazy[2 * v + 1] += lazy[v];
    lazy[v] = 0;
}



void upd(int v, int l, int r, int pos, ll val){
    if(l > pos || r < pos)
        return;
    if(l == r){
        t[v] = val;
        return;
    }
    int m = (l + r) / 2;
    push(v);
    upd(2 * v, l, m, pos, val);
    upd(2 * v + 1, m + 1,r, pos, val);
    t[v] = max(t[2 * v], t[2 * v + 1]);
}

void upd_ran(int v, int l, int r, int st, int fin, ll val){
    if(l > fin || r < st)
        return;
    if(l >= st && r <= fin){
        t[v] += val;
        lazy[v] += val;
        return;
    }
    int m = (l + r) / 2;
    push(v);
    upd_ran(2 * v, l, m, st, fin, val);
    upd_ran(2 * v + 1, m + 1, r, st, fin, val);
    t[v] = max(t[2 * v], t[2 * v + 1]);
}


int main(){
    int n; cin >> n;
    int d; cin >> d;
    ll a[n + 1], b[n + 1];
    ll x[n + 1];
    ll pos[n + 2];
    for(int i = 1; i <= n; i++)
        cin >> x[i] >> a[i] >> b[i];
    map  <int,int> mp;
    vector <pll> cmp;
    for(int i= 1; i <= n; i++){
        cmp.pb({x[i], i});
    }
    cmp.pb({d, 0});
    sort(cmp.begin(), cmp.end());
    for(int i= 0; i < cmp.size(); i++)
        pos[cmp[i].s] = i + 1;
    vector <pll> B;
    for(int i = 1; i <=n; i++){
        B.pb({b[i], i});
    }
    sort(B.begin(), B.end());
    reverse(B.begin(), B.end());
    upd(1, 1, n + 1, n + 1, d);
    for(int i = 1; i<= n; i++)
        upd(1, 1, n + 1, pos[i], x[i]);
    ll ans = d;

    for(int i = 0; i < B.size(); i++){
        int p = B[i].s;
        upd_ran(1, 1, n + 1, pos[p] + 1, n + 1, -a[p]);
        if(B[i].f >= t[1]){
            ans = min(t[1], ans);
            continue;
        }
    }
    cout << max(ans, 0LL);
    return 0;
}

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

FuelStation.cpp: In function 'int main()':
FuelStation.cpp:93:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for(int i= 0; i < cmp.size(); i++)
      |                   ~~^~~~~~~~~~~~
FuelStation.cpp:106:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for(int i = 0; i < B.size(); i++){
      |                    ~~^~~~~~~~~~

• 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