제출 #219280

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
219280		Plasmatic	Pinball (JOI14_pinball)	C++11	51 / 100	1018 ms	65624 KiB

pinball

#pragma GCC optimize "Ofast"
// #pragma GCC optimize "unroll-loops"
#pragma GCC target "sse,sse2,sse3,sse4,abm,avx,avx2,mmx,popcnt,tune=native"

#pragma region
#include "bits/stdc++.h"
using namespace std;
// Common Type shorteners and int128
using ll = long long; using ull = unsigned long long; using ld = long double;
using pii = pair<int, int>; using pll = pair<ll, ll>;
template <typename T> using vec = vector<T>;
template <typename K, typename V> using umap = unordered_map<K, V>; template <typename K> using uset = unordered_set<K>;
using vi = vec<int>; using vl = vec<ll>; using vpi = vec<pii>; using vpl = vec<pll>;
#ifdef __SIZEOF_INT128__
using int128 = __int128_t; using uint128 = __uint128_t;
#endif
template<typename I> string intStr(I x) { string ret; while (x > 0) { ret += (x % 10) + '0'; x /= 10; } reverse(ret.begin(), ret.end()); return ret; } // Int to string
// Shorthand Macros
#define INF 0x3f3f3f3f
#define LLINF 0x3f3f3f3f3f3f3f3f
#define mpr make_pair
#define mtup make_tuple
#define pb push_back
#define popcount __builtin_popcount
#define clz __builtin_clz
#define ctz __builtin_ctz
#define finline __attribute__((always_inline))
// Shorthand Function Macros
#define sz(x) ((int)((x).size()))
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for (__typeof(a) i = a; i < b; i++)
#define reprev(i, a, b) for (__typeof(a) i = a; i > b; i--)
#define repi(a, b) rep(i, a, b)
#define repj(a, b) rep(j, a, b)
#define repk(a, b) rep(k, a, b)
#define Cmplt(type) bool operator<(const type &o) const
#define Cmpgt(type) bool operator>(const type &o) const
#define Cmpfn(name, type) bool name(const type &a, const type &b)
#define Inop(type) istream& operator>>(istream& in, type &o)
#define Outop(type) ostream& operator<<(ostream& out, type o)
#define Pow2(x) (1LL << (x))
#define scn(type, ...) type __VA_ARGS__; scan(__VA_ARGS__) // scn -> Short for SCan New
// Shorthand Functions
template<typename T> inline void maxa(T& st, T v) { st = max(st, v); }
template<typename T> inline void mina(T& st, T v) { st = min(st, v); }
inline void setprec(ostream& out, int prec) { out << setprecision(prec) << fixed; }
// Out operators and printing for arrays and vectors
template <typename T> ostream& operator<<(ostream& out,vector<T> iter){out<<"[";for(auto t:iter){out<<t<<", ";}out<<"]";return out;}
template <typename T> string arrayStr(T *arr,int sz){string ret = "[";for(int i=0;i<sz;i++){ret+=to_string(arr[i])+", "; } return ret + "]";}
template <typename T> void printArray(T *arr,int sz){for(int i=0;i<sz;i++){cout<<arr[i]<<" "; } cout<<"\n";}
// I/O Operations
inline void scan(){}
template<typename F, typename... R> inline void scan(F &f,R&... r){cin>>f;scan(r...);}
template <typename F> inline void println(F t){cout<<t<<'\n';}
template<typename F, typename... R> inline void println(F f,R... r){cout<<f<<" ";println(r...);}
inline void print(){}
template<typename F, typename... R> inline void print(F f,R... r){cout<<f;print(r...);}
// Debugging
#define db(x) cout << (#x) << ": " << (x) << ", "
#define dblb(s) cout << "[" << (s) << "] "
#define dba(alias, x) cout << (alias) << ": " << (x) << ", "
template<typename F> inline string __generic_tostring(F f) { stringstream ss; ss << f; return ss.str(); }
template<typename F> inline string __join_comma(F f) {return __generic_tostring(f);}
template<typename F, typename... R> string __join_comma(F f, R... r) { return __generic_tostring(f) + ", " + __join_comma(r...); }
#define dbp(alias, ...) cout << (alias) << ": (" << __join_comma(__VA_ARGS__) << "), "
#define dbbin(x, n) cout << (#x) << ": " << bitset<n>(x) << ", "
#define dbarr(x, n) cout << (#x) << ": " << arrayStr((x), (n)) << ", "
#define dbln cout << endl;
#pragma endregion

using pil = pair<int, ll>;
struct Sq {
    const int B = 350;
    vec<pil> buf, min, sto;
    void rebuild() {
        if (sz(buf) > B) {
            sort(all(buf));
            sto.insert(sto.end(), all(buf));
            inplace_merge(sto.begin(), sto.end() - sz(buf), sto.end());
            // repi(1, sz(sto))
            //     assert(sto[i - 1].first <= sto[i].first || (sto[i - 1].first == sto[i].first && sto[i - 1].second <= sto[i].second));
            min.clear(); buf.clear();
            ll cmin = LLINF;
            int pre = -1;
            for (auto p : sto) {
                mina(cmin, p.second);
                if (p.first != pre)
                    min.emplace_back(p.first, cmin);
                pre = p.first;
            }
        }
    }
    void upd(int i, ll v) {
        buf.emplace_back(i, v);
    }
    ll ask(int q) {
        rebuild();
        ll res = LLINF;
        if (!min.empty()) {
            auto ptr = upper_bound(all(min), pil{q, LLINF});
            if (ptr != min.begin())
                mina(res, (ptr - 1)->second);
        }
        for (auto &p : buf)
            if (p.first <= q)
                mina(res, p.second);
        return res;
    }
};

struct dev {
    int i, l, r, x, y; ll cost;
    Cmplt(dev) { return r < o.r; }
};

const int MM = 1e5 + 1;
int N, M;
dev devs[MM];
ll dp[2][MM];

Sq bitDown[MM], bitUp[MM];

void upd(Sq bit[MM], int x, int y, ll v) {
    if (v == LLINF) return;
    for (int cx = x; cx <= M; cx += cx & -cx) {
        bit[cx].upd(y, v);
    }
}
ll query(Sq bit[MM], int x, int y) {
    ll res = LLINF;
    for (int cx = x; cx; cx -= cx & -cx) {
        mina(res, bit[cx].ask(y));
    }
    return res;
}

int revX(int x) { return M - x + 1; }
int revY(int y) { return N - y + 1; }

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    scan(M, N);
    repi(1, M + 1) {
        scn(int, a, b, c, d);
        devs[i] = {i, a, b, c, i, d};
    }
    sort(devs + 1, devs + M + 1);

    memset(dp, 0x3f, sizeof dp);
    repi(1, M + 1) {
        // repj(1, i) {
        //     if (devs[j].y < devs[i].y && devs[j].x >= devs[i].l) // transition from above 
        //         mina(dp[0][i], dp[0][j] + devs[i].cost);
        //     if (devs[j].y > devs[i].y && devs[j].r >= devs[i].x) // transition to below!
        //         mina(dp[1][i], min(dp[0][j], dp[1][j]) + devs[i].cost);
        // }
        if (devs[i].l == 1)
            dp[0][i] = devs[i].cost;

        mina(dp[0][i], query(bitDown, devs[i].y - 1, revY(devs[i].l)) + devs[i].cost);
        mina(dp[1][i], query(bitUp, revX(devs[i].y + 1), revY(devs[i].x)) + devs[i].cost);

        upd(bitDown, devs[i].y, revY(devs[i].x), dp[0][i]);
        upd(bitUp, revX(devs[i].y), revY(devs[i].r), min(dp[0][i], dp[1][i]));
    }
    
    ll ans = LLINF;
    repi(1, M + 1)
        if (devs[i].r == N)
            mina(ans, min(dp[0][i], dp[1][i]));
    println(ans == LLINF ? -1 : ans);
    // println(get());

    // dbarr(dp[0], M + 1); dbln;
    // dbarr(dp[1], M + 1); dbln;

    return 0;
}

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

pinball.cpp:5:0: warning: ignoring #pragma region  [-Wunknown-pragmas]
 #pragma region
 
pinball.cpp:69:0: warning: ignoring #pragma endregion  [-Wunknown-pragmas]
 #pragma endregion

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