Submission #494297

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
494297	2021-12-15T02:57:56 Z	rqi	Pinball (JOI14_pinball)	C++14	100 / 100	430 ms	29752 KB

pinball

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef double db; 
typedef string str; 
 
typedef pair<int,int> pi;
typedef pair<ll,ll> pl; 
typedef pair<db,db> pd; 
 
typedef vector<int> vi; 
typedef vector<ll> vl; 
typedef vector<db> vd; 
typedef vector<str> vs; 
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
typedef vector<pd> vpd; 
 
#define mp make_pair 
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#define rsz resize
#define ins insert 
#define ft front() 
#define bk back()
#define pf push_front 
#define pb push_back
#define eb emplace_back 
#define lb lower_bound 
#define ub upper_bound 
 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
 
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; 
const ll INF = 1e18; 
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; 
 
template<class T> bool ckmin(T& a, const T& b) { 
    return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { 
    return a < b ? a = b, 1 : 0; } 
int pct(int x) { return __builtin_popcount(x); } 
int bit(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) 
int cdiv(int a, int b) { return a/b+!(a<0||a%b == 0); } // division of a by b rounded up, assumes b > 0 
 
// INPUT
template<class A> void re(complex<A>& c);
template<class A, class B> void re(pair<A,B>& p);
template<class A> void re(vector<A>& v);
template<class A, size_t SZ> void re(array<A,SZ>& a);
 
template<class T> void re(T& x) { cin >> x; }
void re(db& d) { str t; re(t); d = stod(t); }
void re(ld& d) { str t; re(t); d = stold(t); }
template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }
 
template<class A> void re(complex<A>& c) { A a,b; re(a,b); c = {a,b}; }
template<class A, class B> void re(pair<A,B>& p) { re(p.f,p.s); }
template<class A> void re(vector<A>& x) { trav(a,x) re(a); }
template<class A, size_t SZ> void re(array<A,SZ>& x) { trav(a,x) re(a); }
 
// TO_STRING
#define ts to_string
template<class A, class B> str ts(pair<A,B> p);
template<class A> str ts(complex<A> c) { return ts(mp(c.real(),c.imag())); }
str ts(bool b) { return b ? "true" : "false"; }
str ts(char c) { str s = ""; s += c; return s; }
str ts(str s) { return s; }
str ts(const char* s) { return (str)s; }
str ts(vector<bool> v) { 
    bool fst = 1; str res = "{";
    F0R(i,sz(v)) {
        if (!fst) res += ", ";
        fst = 0; res += ts(v[i]);
    }
    res += "}"; return res;
}
template<size_t SZ> str ts(bitset<SZ> b) {
    str res = ""; F0R(i,SZ) res += char('0'+b[i]);
    return res; }
template<class T> str ts(T v) {
    bool fst = 1; str res = "{";
    for (const auto& x: v) {
        if (!fst) res += ", ";
        fst = 0; res += ts(x);
    }
    res += "}"; return res;
}
template<class A, class B> str ts(pair<A,B> p) {
    return "("+ts(p.f)+", "+ts(p.s)+")"; }
 
// OUTPUT
template<class A> void pr(A x) { cout << ts(x); }
template<class H, class... T> void pr(const H& h, const T&... t) { 
    pr(h); pr(t...); }
void ps() { pr("\n"); } // print w/ spaces
template<class H, class... T> void ps(const H& h, const T&... t) { 
    pr(h); if (sizeof...(t)) pr(" "); ps(t...); }
 
// DEBUG
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
    DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 42
#endif
 
// FILE I/O
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
void setIO(string s = "") {
    unsyncIO();
    // cin.exceptions(cin.failbit); 
    // throws exception when do smth illegal
    // ex. try to read letter into int
    if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}
 
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 
 
/**
 * Description: 1D point update, range query where \texttt{comb} is
     * any associative operation. If $N$ is not power of 2 then 
     * operations work but \texttt{seg[1] != query(0,N-1)}.
 * Time: O(\log N)
 * Source: 
    * http://codeforces.com/blog/entry/18051
    * KACTL
 * Verification: SPOJ Fenwick
 */
 
template<class T> struct Seg { // comb(ID,b) = b
    const T ID = INF; T comb(T a, T b) { return min(a, b); } 
    int n; vector<T> seg;
    void init(int _n) { n = _n; seg.assign(2*n,ID); }
    void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }
    void upd(int p, T val) { // min val at position p
        ckmin(seg[p+=n], val);
        for (p /= 2; p; p /= 2) pull(p); }
    T query(int l, int r) {    // sum on interval [l, r]
        T ra = ID, rb = ID; 
        for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
            if (l&1) ra = comb(ra,seg[l++]);
            if (r&1) rb = comb(seg[--r],rb);
        }
        return comb(ra,rb);
    }
};
 
 
 
const int mx = 300007;
int A[mx];
int B[mx];
int C[mx];
ll D[mx];
map<int, int> m;
 
Seg<ll> fL; // fixed L value
Seg<ll> fR; // fixed R value
 
 
int main() {
    setIO();
    fL.init(mx);
    fR.init(mx);
    int M, N;
    cin >> M >> N;
    for(int i = 1; i <= M; i++){
        cin >> A[i] >> B[i] >> C[i] >> D[i];
        m[A[i]];
        m[B[i]];
        if(B[i]+1 <= N) m[B[i]+1];
        //dbg(i, A[i], B[i], C[i]);
    }
    m[1];
    m[N];
    int cnt = 0;
    for(auto &u: m){
        cnt++;
        u.s = cnt;
    }
    //dbg(m);
    for(int i = 1; i <= M; i++){
        A[i] = m[A[i]];
        B[i] = m[B[i]];
        C[i] = (prev(m.ub(C[i])))->s;
        //dbg(i, A[i], B[i], C[i]);
    }
    N = m[N];
    ////////////////////////
    ll ans = INF;
    fL.upd(1, 0);
    fR.upd(N, 0);
    for(int i = 1; i <= M; i++){
        ckmin(ans, fL.query(A[i], B[i])+fR.query(A[i], B[i])+D[i]);
        fL.upd(C[i], fL.query(A[i], C[i])+D[i]);
        fR.upd(C[i], fR.query(C[i], B[i])+D[i]);
    }
    if(ans == INF) ps(-1);
    else ps(ans);
    // you should actually read the stuff at the bottom
}
 
/* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?)
    * do smth instead of nothing and stay organized
    * WRITE STUFF DOWN
*/

Compilation message

pinball.cpp: In function 'void setIn(std::string)':
pinball.cpp:123:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 | void setIn(string s) { freopen(s.c_str(),"r",stdin); }
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
pinball.cpp: In function 'void setOut(std::string)':
pinball.cpp:124:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 | void setOut(string s) { freopen(s.c_str(),"w",stdout); }
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	9724 KB	Output is correct
2	Correct	4 ms	9676 KB	Output is correct
3	Correct	4 ms	9676 KB	Output is correct
4	Correct	5 ms	9728 KB	Output is correct
5	Correct	4 ms	9676 KB	Output is correct
6	Correct	4 ms	9732 KB	Output is correct
7	Correct	4 ms	9676 KB	Output is correct
8	Correct	4 ms	9628 KB	Output is correct

Subtask #2

18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	9724 KB	Output is correct
2	Correct	4 ms	9676 KB	Output is correct
3	Correct	4 ms	9676 KB	Output is correct
4	Correct	5 ms	9728 KB	Output is correct
5	Correct	4 ms	9676 KB	Output is correct
6	Correct	4 ms	9732 KB	Output is correct
7	Correct	4 ms	9676 KB	Output is correct
8	Correct	4 ms	9628 KB	Output is correct
9	Correct	5 ms	9676 KB	Output is correct
10	Correct	5 ms	9736 KB	Output is correct
11	Correct	4 ms	9676 KB	Output is correct
12	Correct	5 ms	9740 KB	Output is correct
13	Correct	5 ms	9740 KB	Output is correct
14	Correct	6 ms	9676 KB	Output is correct

Subtask #3

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	9724 KB	Output is correct
2	Correct	4 ms	9676 KB	Output is correct
3	Correct	4 ms	9676 KB	Output is correct
4	Correct	5 ms	9728 KB	Output is correct
5	Correct	4 ms	9676 KB	Output is correct
6	Correct	4 ms	9732 KB	Output is correct
7	Correct	4 ms	9676 KB	Output is correct
8	Correct	4 ms	9628 KB	Output is correct
9	Correct	5 ms	9676 KB	Output is correct
10	Correct	5 ms	9736 KB	Output is correct
11	Correct	4 ms	9676 KB	Output is correct
12	Correct	5 ms	9740 KB	Output is correct
13	Correct	5 ms	9740 KB	Output is correct
14	Correct	6 ms	9676 KB	Output is correct
15	Correct	5 ms	9676 KB	Output is correct
16	Correct	5 ms	9744 KB	Output is correct
17	Correct	6 ms	9804 KB	Output is correct
18	Correct	5 ms	9752 KB	Output is correct
19	Correct	6 ms	9812 KB	Output is correct
20	Correct	6 ms	9748 KB	Output is correct
21	Correct	5 ms	9804 KB	Output is correct
22	Correct	6 ms	9864 KB	Output is correct
23	Correct	6 ms	9948 KB	Output is correct
24	Correct	6 ms	9932 KB	Output is correct

Subtask #4

49.0 / 49.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	9724 KB	Output is correct
2	Correct	4 ms	9676 KB	Output is correct
3	Correct	4 ms	9676 KB	Output is correct
4	Correct	5 ms	9728 KB	Output is correct
5	Correct	4 ms	9676 KB	Output is correct
6	Correct	4 ms	9732 KB	Output is correct
7	Correct	4 ms	9676 KB	Output is correct
8	Correct	4 ms	9628 KB	Output is correct
9	Correct	5 ms	9676 KB	Output is correct
10	Correct	5 ms	9736 KB	Output is correct
11	Correct	4 ms	9676 KB	Output is correct
12	Correct	5 ms	9740 KB	Output is correct
13	Correct	5 ms	9740 KB	Output is correct
14	Correct	6 ms	9676 KB	Output is correct
15	Correct	5 ms	9676 KB	Output is correct
16	Correct	5 ms	9744 KB	Output is correct
17	Correct	6 ms	9804 KB	Output is correct
18	Correct	5 ms	9752 KB	Output is correct
19	Correct	6 ms	9812 KB	Output is correct
20	Correct	6 ms	9748 KB	Output is correct
21	Correct	5 ms	9804 KB	Output is correct
22	Correct	6 ms	9864 KB	Output is correct
23	Correct	6 ms	9948 KB	Output is correct
24	Correct	6 ms	9932 KB	Output is correct
25	Correct	23 ms	10956 KB	Output is correct
26	Correct	64 ms	13752 KB	Output is correct
27	Correct	243 ms	18512 KB	Output is correct
28	Correct	135 ms	15472 KB	Output is correct
29	Correct	153 ms	17128 KB	Output is correct
30	Correct	177 ms	16412 KB	Output is correct
31	Correct	386 ms	23596 KB	Output is correct
32	Correct	293 ms	21508 KB	Output is correct
33	Correct	37 ms	13448 KB	Output is correct
34	Correct	148 ms	19672 KB	Output is correct
35	Correct	168 ms	29640 KB	Output is correct
36	Correct	430 ms	29752 KB	Output is correct
37	Correct	309 ms	29624 KB	Output is correct
38	Correct	296 ms	29636 KB	Output is correct