oj.uz

답안 #295293

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
295293 2020-09-09T15:07:26 Z 반딧불(#5812) 치료 계획 (JOI20_treatment) C++17
0 / 100
 111 ms 36064 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Plan{
    ll t, l, r, cost;
    Plan(){}
    Plan(ll t, ll l, ll r, ll cost): t(t), l(l), r(r), cost(cost){}
};

struct Point{
    ll x, y; int idx;
    Point(){}
    Point(ll x, ll y, int idx): x(x), y(y), idx(idx){}

    bool operator<(const Point &r)const{
        return y>r.y;
    }
};

struct dat{
    int x; ll y;
    dat(){}
    dat(int x, ll y): x(x), y(y){}

    bool operator<(const dat &r)const{
        return y>r.y;
    }
};

vector<int> retVal;
struct segTree{
    vector<Point> tree[400002];
    void initialize(int i, int l, int r){
        sort(tree[i].begin(), tree[i].end());
        if(l==r) return;
        int m = (l+r)>>1;
        initialize(i*2, l, m), initialize(i*2+1, m+1, r);
    }
    void pushPoint(int i, int l, int r, Point p){
        tree[i].push_back(p);
        if(l==r) return;
        int m = (l+r)>>1;
        if(p.x <= m) pushPoint(i*2, l, m, p);
        else pushPoint(i*2+1, m+1, r, p);
    }

    void rectQuery(int i, int l, int r, int xLim, ll yLim){
        if(xLim < l) return;
        if(r<=xLim){
            while(!tree[i].empty() && tree[i].back().y <= yLim){
                retVal.push_back(tree[i].back().idx);
                tree[i].pop_back();
            }
            return;
        }
        int m = (l+r)>>1;
        rectQuery(i*2, l, m, xLim, yLim), rectQuery(i*2+1, m+1, r, xLim, yLim);
    }
} tree;

int n, m;
Plan arr[100002];
bool chk[100002];
ll ans = LLONG_MAX;
priority_queue<dat> pq;
vector<Point> pointVec;
vector<ll> renVec;

void makeSegTree(){
    for(auto &x: pointVec) renVec.push_back(x.x);
    sort(renVec.begin(), renVec.end());
    renVec.erase(unique(renVec.begin(), renVec.end()), renVec.end());
    for(auto &x: pointVec) x.x = lower_bound(renVec.begin(), renVec.end(), x.x) - renVec.begin() + 1;

    for(auto &x: pointVec) tree.pushPoint(1, 1, n, x);
    tree.initialize(1, 1, n);
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=m; i++){
        scanf("%lld %lld %lld %lld", &arr[i].t, &arr[i].l, &arr[i].r, &arr[i].cost);
        arr[i].r++;
        if(arr[i].l == 1) pq.push(dat(i, arr[i].cost));
        else pointVec.push_back(Point(arr[i].l + arr[i].t, arr[i].l - arr[i].t, i));
    }

    makeSegTree();

    while(!pq.empty()){
        auto tmp = pq.top(); pq.pop();
        if(chk[tmp.x]) continue;
        int tx = tmp.x; ll ty = tmp.y;
        chk[tx] = 1;
        if(arr[tx].r == n+1) ans = min(ans, ty);

        int xLim = arr[tx].r + arr[tx].t; ll yLim = arr[tx].r - arr[tx].t;
        xLim = upper_bound(renVec.begin(), renVec.end(), xLim) - renVec.begin();

        retVal.clear(); retVal.shrink_to_fit();
        tree.rectQuery(1, 1, n, xLim, yLim);
        for(auto nxt: retVal){
            if(chk[nxt]) continue;
            pq.push(dat(nxt, ty+arr[nxt].cost));
        }
    }
    printf("%lld", ans == LLONG_MAX ? -1 : ans);
}

Compilation message

treatment.cpp: In function 'int main()':
treatment.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   83 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
treatment.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   85 |         scanf("%lld %lld %lld %lld", &arr[i].t, &arr[i].l, &arr[i].r, &arr[i].cost);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 111 ms 36064 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Runtime error 19 ms 19456 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Runtime error 19 ms 19456 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 111 ms 36064 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -