제출 #584471

#제출 시각아이디문제언어결과실행 시간메모리
584471dxz05Pinball (JOI14_pinball)C++14
100 / 100
507 ms38824 KiB
#pragma GCC optimize("Ofast,O2,O3,unroll-loops") #pragma GCC target("avx2") #include <bits/stdc++.h> #include <random> using namespace std; void debug_out() { cerr << endl; } template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << "[" << H << "]"; debug_out(T...); } #ifdef dddxxz #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #else #define debug(...) 42 #endif #define SZ(s) ((int)s.size()) #define all(x) (x).begin(), (x).end() #define lla(x) (x).rbegin(), (x).rend() #define bpc(x) __builtin_popcount(x) #define bpcll(x) __builtin_popcountll(x) clock_t startTime; double getCurrentTime() { return (double) (clock() - startTime) / CLOCKS_PER_SEC; } #define MP make_pair typedef long long ll; mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const double eps = 0.000001; const int MOD = 1e9 + 7; const int INF = 1000000101; const long long LLINF = 1223372000000000555; const int N = 2e6 + 3e2; const int M = 1111; struct SegTree{ int size = 1; vector<ll> t; SegTree(int n){ t.assign(4 * n + 5, LLINF); size = n; } void update(int v, int tl, int tr, int pos, ll val){ if (tl == tr){ t[v] = min(t[v], val); return; } int tm = (tl + tr) >> 1; if (pos <= tm) update(v << 1, tl, tm, pos, val); else update(v << 1 | 1, tm + 1, tr, pos, val); t[v] = min(t[v << 1], t[v << 1 | 1]); } void update(int pos, ll val){ update(1, 1, size, pos, val); } ll get(int v, int tl, int tr, int l, int r){ if (l <= tl && tr <= r) return t[v]; if (tl > r || tr < l) return LLINF; int tm = (tl + tr) >> 1; return min(get(v << 1, tl, tm, l, r), get(v << 1 | 1, tm + 1, tr, l, r)); } ll get(int l, int r){ return get(1, 1, size, l, r); } }; long long pinball(int m, int n, vector<int> a, vector<int> b, vector<int> c, vector<int> d) { map<int, int> mp; mp[1] = mp[n] = 0; for (int i = 0; i < m; i++){ mp[a[i]] = mp[b[i]] = mp[c[i]] = 0; } n = 0; for (auto &now : mp) now.second = ++n; for (int i = 0; i < m; i++){ a[i] = mp[a[i]]; b[i] = mp[b[i]]; c[i] = mp[c[i]]; } vector<ll> dp1(m, LLINF), dp2(m, LLINF); SegTree st1(n), st2(n); ll ans = LLINF; for (int i = 0; i < m; i++){ if (a[i] == 1){ dp1[i] = d[i]; } else { dp1[i] = st1.get(a[i], b[i]) + d[i]; } if (b[i] == n){ dp2[i] = d[i]; } else { dp2[i] = st2.get(a[i], b[i]) + d[i]; } debug(dp1[i], dp2[i]); ans = min(ans, dp1[i] + dp2[i] - d[i]); st1.update(c[i], dp1[i]); st2.update(c[i], dp2[i]); } if (ans > 1e16) ans = -1; return ans; } void solve(int TC) { int m, n; cin >> m >> n; vector<int> a(m), b(m), c(m), d(m); for (int i = 0; i < m; i++) cin >> a[i] >> b[i] >> c[i] >> d[i]; cout << pinball(m, n, a, b, c, d) << endl; } int main() { startTime = clock(); ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); #ifdef dddxxz freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif int TC = 1; // cin >> TC; for (int test = 1; test <= TC; test++) { //debug(test); //cout << "Case #" << test << ": "; solve(test); } #ifdef dddxxz cerr << endl << "Time: " << int(getCurrentTime() * 1000) << " ms" << endl; #endif return 0; }

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

pinball.cpp: In function 'long long int pinball(int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
pinball.cpp:21:20: warning: statement has no effect [-Wunused-value]
   21 | #define debug(...) 42
      |                    ^~
pinball.cpp:116:9: note: in expansion of macro 'debug'
  116 |         debug(dp1[i], dp2[i]);
      |         ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...