제출 #209480

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
209480		balbit	Sky Walking (IOI19_walk)	C++14	15 / 100	363 ms	71560 KiB

walk

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define ALL(x) x.begin(),x.end()
#define SZ(x) x.size()
#define pb push_back


#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<": ",_do(__VA_ARGS__)
template<typename T> void _do(T &&x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y){cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios::sync_with_stdio(0)
#define endl '\n'
#define bug(...)
#endif // BALBIT


const int maxn = 1e6;

struct Br{
    int l,r,y;
};
struct Bd{
    int x, y;
};

#define pli pair<ll, int>
#define pii pair<int, int>
#define f first
#define s second

vector<pii> g[maxn*2];

ll min_distance(vector<signed> x, vector<signed> h, vector<signed> il, vector<signed> ir, vector<signed> iy, signed startx, signed endx) {
    int n = SZ(x), m = SZ(il);
    vector<pii> in, out;
    for (int i = 0; i<m; ++i) {
        in.pb({il[i], iy[i]});
        out.pb({ir[i], iy[i]});
    }
    in.pb({0,0});
    out.pb({0,0});

    in.pb({n-1,0});
    out.pb({n-1,0});

    sort(ALL(in), [&](pii a, pii b){return a.f!=b.f?a.f<b.f:a.s>b.s;});
    sort(ALL(out), [&](pii a, pii b){return a.f!=b.f?a.f<b.f:a.s>b.s;});

    m+=2;

//    sort(ALL(bds), [&](Bd a, Bd b) { return a.y > b.y; });
    map<int, int> cut;
    vector<map<int, int> > hv(n);
    int ID = 0;
    int oj = 0, ij = 0;
    int S, T;
//    set<int> dontkill;
    map<int, int> ans; // answer for this
    for (int i = 0; i<n; ++i) {
//        set<int> app; // newly appeared
        while (ij < m && in[ij].f <= i) {
            int H = in[ij].s;
            if (cut[H]==0) {
//                app.insert(H);
                if (i == 0) {
                    ans[H] = H;
                }else{
                    ans[H] = 0x3f3f3f3f3f3f3f3f;
                    auto iter = ans.upper_bound(H);
                    if (iter!=ans.end()) {
                        ans[H] = iter->s + abs((iter-> f)- H);
                    }
                    if (--iter!=ans.begin()) {
                        --iter;
                        bug(H, "down", iter->f);
                        ans[H] = min(ans[H], iter->s + abs((iter-> f)- H));
                    }
                }
                bug(H, ans[H]);
            }else{
                bug(H, cut[H]);
            }
            ++cut[(H)];
            ++ij;
            if (H == 0 && i==n-1) {
                bug(H, ans[H]);
                if (ans[H] == 0x3f3f3f3f3f3f3f3f) return -1;
                return ans[H] + x[n-1] - x[0];
            }
        }
////        bug(i, SZ(cut));
//        int prvid = ID++, prvh = 0;
//        if (i == startx) S = prvid;
//        if (i == endx) T = prvid;

        while (oj < m && out[oj].f <= i) {
            --cut[out[oj].s];
            bug("minus",out[oj].s);
            if (cut[out[oj].s] == 0) {
                cut.erase(out[oj].s);
                ans.erase(out[oj].s);
            }

            ++oj;
        }

    }
//    bug(ID, S, T);
//    vector<ll> d(ID, 0x3f3f3f3f3f3f3f3f);
//    priority_queue<pli, vector<pli >, greater<pli> > pq;
//    d[S] = 0;
//    pq.push({0,S});
//    while (!pq.empty()) {
//        ll w = pq.top().f;
//        int v = pq.top().s;
//        pq.pop();
//        if (d[v] != w) continue;
//        for (pii u : g[v]) {
//            if (d[u.f] > w + u.s) {
//                d[u.f] = w + u.s;
//                pq.push({d[u.f], u.f});
//            }
//        }
//    }
//    for (int i = 0; i<ID; i++) {
//        for (pii u : g[i]) {
//            bug(i,u.f, u.s);
//        }
//    }
//    for (int i = 0; i<ID; i++) {
//        bug(i, d[i]);
//    }
//    if (d[T] == 0x3f3f3f3f3f3f3f3f) d[T] = -1;
    return -1;

}

#ifdef BALBIT
signed main(){
    IOS();
//    int MO = min_distance({0, 4, 5, 6, 9},
//{6, 6, 6, 6, 6},
//{3, 1, 0},
//{4, 3, 2},
//{1, 3, 6},
//0, 4);
//    bug(MO);
    int MO2 = min_distance({0, 3, 5, 7, 10, 12, 14},
{8, 7, 9, 7, 6, 6, 9},
{0, 0, 0, 2, 2, 3, 4, 5},
{1, 2, 6, 3, 6, 4, 5, 6},
{1, 6, 8, 1, 7, 2, 5, 5},
0, 6);
    bug(MO2);
}
#endif

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

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:59:9: warning: unused variable 'ID' [-Wunused-variable]
     int ID = 0;
         ^~
walk.cpp:61:9: warning: unused variable 'S' [-Wunused-variable]
     int S, T;
         ^
walk.cpp:61:12: warning: unused variable 'T' [-Wunused-variable]
     int S, T;
            ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 15 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43