oj.uz

Submission #219280

# Submission time Handle Problem Language Result Execution time Memory
219280 2020-04-05T02:36:06 Z Plasmatic Pinball (JOI14_pinball) C++11
51 / 100
 1000 ms 65624 KB 
#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;
}

Compilation message

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 17536 KB Output is correct
2 Correct 15 ms 17536 KB Output is correct
3 Correct 15 ms 17536 KB Output is correct
4 Correct 17 ms 17536 KB Output is correct
5 Correct 15 ms 17536 KB Output is correct
6 Correct 15 ms 17536 KB Output is correct
7 Correct 15 ms 17536 KB Output is correct
8 Correct 15 ms 17536 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 17536 KB Output is correct
2 Correct 15 ms 17536 KB Output is correct
3 Correct 15 ms 17536 KB Output is correct
4 Correct 17 ms 17536 KB Output is correct
5 Correct 15 ms 17536 KB Output is correct
6 Correct 15 ms 17536 KB Output is correct
7 Correct 15 ms 17536 KB Output is correct
8 Correct 15 ms 17536 KB Output is correct
9 Correct 16 ms 17536 KB Output is correct
10 Correct 15 ms 17664 KB Output is correct
11 Correct 15 ms 17664 KB Output is correct
12 Correct 15 ms 17536 KB Output is correct
13 Correct 15 ms 17536 KB Output is correct
14 Correct 15 ms 17536 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 17536 KB Output is correct
2 Correct 15 ms 17536 KB Output is correct
3 Correct 15 ms 17536 KB Output is correct
4 Correct 17 ms 17536 KB Output is correct
5 Correct 15 ms 17536 KB Output is correct
6 Correct 15 ms 17536 KB Output is correct
7 Correct 15 ms 17536 KB Output is correct
8 Correct 15 ms 17536 KB Output is correct
9 Correct 16 ms 17536 KB Output is correct
10 Correct 15 ms 17664 KB Output is correct
11 Correct 15 ms 17664 KB Output is correct
12 Correct 15 ms 17536 KB Output is correct
13 Correct 15 ms 17536 KB Output is correct
14 Correct 15 ms 17536 KB Output is correct
15 Correct 15 ms 17664 KB Output is correct
16 Correct 15 ms 17664 KB Output is correct
17 Correct 17 ms 17664 KB Output is correct
18 Correct 17 ms 17792 KB Output is correct
19 Correct 16 ms 17664 KB Output is correct
20 Correct 17 ms 17792 KB Output is correct
21 Correct 15 ms 17664 KB Output is correct
22 Correct 16 ms 17664 KB Output is correct
23 Correct 16 ms 17792 KB Output is correct
24 Correct 16 ms 17664 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 17536 KB Output is correct
2 Correct 15 ms 17536 KB Output is correct
3 Correct 15 ms 17536 KB Output is correct
4 Correct 17 ms 17536 KB Output is correct
5 Correct 15 ms 17536 KB Output is correct
6 Correct 15 ms 17536 KB Output is correct
7 Correct 15 ms 17536 KB Output is correct
8 Correct 15 ms 17536 KB Output is correct
9 Correct 16 ms 17536 KB Output is correct
10 Correct 15 ms 17664 KB Output is correct
11 Correct 15 ms 17664 KB Output is correct
12 Correct 15 ms 17536 KB Output is correct
13 Correct 15 ms 17536 KB Output is correct
14 Correct 15 ms 17536 KB Output is correct
15 Correct 15 ms 17664 KB Output is correct
16 Correct 15 ms 17664 KB Output is correct
17 Correct 17 ms 17664 KB Output is correct
18 Correct 17 ms 17792 KB Output is correct
19 Correct 16 ms 17664 KB Output is correct
20 Correct 17 ms 17792 KB Output is correct
21 Correct 15 ms 17664 KB Output is correct
22 Correct 16 ms 17664 KB Output is correct
23 Correct 16 ms 17792 KB Output is correct
24 Correct 16 ms 17664 KB Output is correct
25 Correct 48 ms 21240 KB Output is correct
26 Correct 128 ms 27688 KB Output is correct
27 Correct 623 ms 52244 KB Output is correct
28 Execution timed out 1018 ms 65624 KB Time limit exceeded
29 Halted 0 ms 0 KB -