제출 #330486

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
330486		SnowFlake7	Pinball (JOI14_pinball)	C++14	100 / 100	934 ms	33628 KiB

pinball

#include <bits/stdc++.h>

using namespace std;

const long long MX_VAL = 1e18;
long long a[100005],b[100005],c[100005],d[100005];
long long aint[2000005],dp1[100005],dp2[100005];
map <int, int> mp;
vector <int> v;

void update(int nod, int st, int dr, int poz, long long val) {
    if (st == dr)
        aint[nod] = min(aint[nod], val);
    else {
        int md = (st + dr) / 2;
        if (poz <= md)
            update(2 * nod, st, md, poz, val);
        if (poz >= md + 1)
            update (2 * nod + 1, md + 1, dr, poz, val);
        aint[nod] = min(aint[2 * nod], aint[2 * nod + 1]);
    }
}
long long query(int nod, int st, int dr, int a, int b) {
    if (a <= st && dr <= b)
        return aint[nod];
    else {
        int md = (st + dr) / 2;
        long long ans = MX_VAL;
        if (a <= md)
        ans = min(ans, query(2 * nod, st, md, a, b));
        if (b >= md + 1)
            ans = min(ans, query(2 * nod + 1, md + 1, dr, a, b));
        return ans;
    }
}
int main ()
{
    long long n,m,nr = 0,ans = MX_VAL;
    cin >> m >> n;
    for (int i = 1;i <= m;i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        v.push_back(a[i]);
        v.push_back(b[i]);
        v.push_back(c[i]);
    }
    sort(v.begin(), v.end());
    for (int i = 0;i < v.size();i++) {
        if (!i || v[i] != v[i - 1])
            mp[v[i]] = ++nr;
    }
    for (int i = 1; i <= 4 * nr;i++)
        aint[i] = MX_VAL;
    for (int i = 1;i <= m;i++)
        dp1[i] = dp2[i] = MX_VAL;
    for (int i = 1;i <= m;i++) {
        if (a[i] == 1)
            dp1[i] = d[i];
        else
            dp1[i] = min(dp1[i], d[i] + query(1, 1, nr, mp[a[i]], mp[b[i]]));
        update(1, 1, nr, mp[c[i]], dp1[i]);
    }
    for (int i = 1;i <= 4 * nr;i++)
        aint[i] = MX_VAL;
    for (int i = 1;i <= m;i++) {
        if (b[i] == n)
            dp2[i] = d[i];
        else
            dp2[i] = min(dp2[i], d[i] + query(1, 1, nr, mp[a[i]], mp[b[i]]));
        update(1, 1, nr, mp[c[i]], dp2[i]);
    }
    for (int i = 1;i <= m;i++)
        ans = min(ans, dp1[i] + dp2[i] - d[i]);
    if (ans == MX_VAL)
        ans = -1;
    cout << ans;
    return 0;
}

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

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

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 49 / 49