제출 #1048029

#제출 시각아이디문제언어결과실행 시간메모리
1048029TsovakText editor (CEOI24_editor)C++17
16 / 100
458 ms363856 KiB
// -------------------- Includes -------------------- // #define _CRT_SECURE_NO_WARNINGS #define _USE_MATH_DEFINES #include <iostream> #include <iomanip> #include <cstdio> #include <stdio.h> #include <cstdlib> #include <stdlib.h> #include <array> #include <string> #include <cstring> #include <algorithm> #include <cmath> #include <math.h> #include <set> #include <map> #include <unordered_set> #include <unordered_map> #include <vector> #include <stack> #include <queue> #include <deque> #include <bitset> #include <list> #include <iterator> #include <numeric> #include <complex> #include <tuple> #include <utility> #include <cassert> #include <assert.h> #include <climits> #include <limits.h> #include <ctime> #include <time.h> #include <random> #include <chrono> #include <fstream> using namespace std; // -------------------- Typedefs -------------------- // typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ld; // -------------------- Defines -------------------- // #define pr pair #define mpr make_pair #define ff first #define ss second #define mset multiset #define mmap multimap #define uset unordered_set #define umap unordered_map #define umset unordered_multiset #define ummap unordered_multimap #define pqueue priority_queue #define sz(x) (int((x).size())) #define len(x) (int((x).length())) #define all(x) (x).begin(), (x).end() #define clr(x) (x).clear() #define ft front #define bk back #define pf push_front #define pb push_back #define popf pop_front #define popb pop_back #define lb lower_bound #define ub upper_bound #define bs binary_search // -------------------- Constants -------------------- // const int MAX = int(1e9 + 5); const ll MAXL = ll(1e18 + 5); const ll MOD = ll(1e9 + 7); const ll MOD2 = ll(998244353); // -------------------- Functions -------------------- // void fastio() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); return; } void precision(int x) { cout << fixed << setprecision(x); return; } ll gcd0(ll a, ll b) { while (b) { a %= b; swap(a, b); } return a; } ll lcm0(ll a, ll b) { return a / gcd0(a, b) * b; } bool is_prime(ll a) { if (a == 1) return false; for (ll i = 2; i * i <= a; i++) if (a % i == 0) return false; return true; } bool is_square(ll a) { ll b = ll(sqrtl(ld(a))); return (b * b == a); } bool is_cube(ll a) { ll b = ll(cbrtl(ld(a))); return (b * b * b == a); } int digit_sum(ll a) { int sum = 0; while (a) { sum += int(a % 10); a /= 10; } return sum; } ll binpow(ll a, int b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll binpow_mod(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1) ans = (ans * a) % mod; b >>= 1; a = (a * a) % mod; } return ans; } ll factorial(int a) { ll ans = 1; for (int i = 2; i <= a; i++) ans *= ll(i); return ans; } ll factorial_mod(int a, ll mod) { ll ans = 1; for (int i = 2; i <= a; i++) ans = (ans * ll(i)) % mod; return ans; } // -------------------- Solution -------------------- // const int N = 1'000'006; ll a[N]; int ul[N], ur[N]; vector<pr<int, ll>> g[N * 2]; int n; ll dist[N * 2]; set<pr<ll, int>> st; void dijkstra() { int i, j; int u, v; ll w; fill(dist, dist + n * 2 + 3, MAXL); dist[0] = 0; st.insert(mpr(0, 0)); while (!st.empty()) { u = (*st.begin()).ss; st.erase(st.begin()); for (i = 0; i < sz(g[u]); i++) { v = g[u][i].ff; w = g[u][i].ss; if (dist[v] > dist[u] + w) { st.erase(mpr(dist[v], v)); dist[v] = dist[u] + w; st.insert(mpr(dist[v], v)); } } } return; } void solve() { int i, j; int x, z; ll y, t; cin >> n; cin >> x >> y >> z >> t; for (i = 1; i <= n; i++) { cin >> a[i]; a[i]++; } stack<pr<int, int>> s; for (i = 1; i <= n; i++) { while (!s.empty() && s.top().ff > a[i]) s.pop(); if (!s.empty()) ul[i] = s.top().ss; s.push(mpr(a[i], i)); } while (!s.empty()) s.pop(); for (i = n; i >= 1; i--) { while (!s.empty() && s.top().ff > a[i]) s.pop(); if (!s.empty()) ur[i] = s.top().ss; else ur[i] = n + 1; s.push(mpr(a[i], i)); } // same line for (i = 1; i <= n; i++) { g[i * 2 - 1].pb(mpr(i * 2, a[i] - 1)); g[i * 2].pb(mpr(i * 2 - 1, a[i] - 1)); } // adjacent line for (i = 1; i < n; i++) { g[i * 2 - 1].pb(mpr(i * 2 + 1, 1)); g[i * 2 + 1].pb(mpr(i * 2 - 1, 1)); g[i * 2].pb(mpr(i * 2 + 1, 1)); g[i * 2 + 1].pb(mpr(i * 2, 1)); } // closest smaller for (i = 1; i <= n; i++) { if (ul[i]) { g[i * 2].pb(mpr(ul[i] * 2, i - ul[i])); g[ul[i] * 2].pb(mpr(i * 2, i - ul[i] + a[i] - a[ul[i]])); } if (ur[i] <= n) { g[i * 2].pb(mpr(ur[i] * 2, ur[i] - i)); g[ur[i] * 2].pb(mpr(i * 2, ur[i] - i + a[i] - a[ur[i]])); } } // same line for start and end g[0].pb(mpr(x * 2 - 1, y - 1)); g[x * 2 - 1].pb(mpr(0, y - 1)); g[0].pb(mpr(x * 2, a[x] - y)); g[x * 2].pb(mpr(0, a[x] - y)); g[n * 2 + 1].pb(mpr(z * 2 - 1, t - 1)); g[z * 2 - 1].pb(mpr(n * 2 + 1, t - 1)); g[n * 2 + 1].pb(mpr(z * 2, a[z] - t)); g[z * 2].pb(mpr(n * 2 + 1, a[z] - t)); // closest smaller for start for (i = x - 1; i >= 1; i--) { if (a[i] <= y) { g[0].pb(mpr(i * 2, x - i)); g[i * 2].pb(mpr(0, x - i + y - a[i])); break; } } for (i = x + 1; i <= n; i++) { if (a[i] <= y) { g[0].pb(mpr(i * 2, i - x)); g[i * 2].pb(mpr(0, i - x + y - a[i])); break; } } // closest smaller for end for (i = z - 1; i >= 1; i--) { if (a[i] <= t) { g[n * 2 + 1].pb(mpr(i * 2, z - i)); g[i * 2].pb(mpr(n * 2 + 1, z - i + t - a[i])); break; } } for (i = z + 1; i <= n; i++) { if (a[i] <= t) { g[n * 2 + 1].pb(mpr(i * 2, i - z)); g[i * 2].pb(mpr(n * 2 + 1, i - z + t - a[i])); break; } } dijkstra(); ll mn = min(y, t); for (i = min(x, z) + 1; i < max(x, z); i++) mn = min(mn, a[i]); cout << min(dist[n * 2 + 1], llabs(x - z) + (y - mn) + (t - mn)) << "\n"; return; } void precalc() { return; } int main() { fastio(); precalc(); int tests = 1, tc; //cin >> tests; for (tc = 1; tc <= tests; tc++) { solve(); } return 0; } /* # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # */

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

Main.cpp: In function 'void dijkstra()':
Main.cpp:196:9: warning: unused variable 'j' [-Wunused-variable]
  196 |  int i, j;
      |         ^
Main.cpp: In function 'void solve()':
Main.cpp:225:9: warning: unused variable 'j' [-Wunused-variable]
  225 |  int i, j;
      |         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...