제출 #413222

#제출 시각아이디문제언어결과실행 시간메모리
413222usachevd0모임들 (IOI18_meetings)C++14
0 / 100
1504 ms786432 KiB
#include <bits/stdc++.h> #ifndef LOCAL #include "meetings.h" #endif using namespace std; #define fi first #define se second #define mp make_pair #define pb push_back #define all(a) (a).begin(), (a).end() #define Time (clock() * 1.0 / CLOCKS_PER_SEC) using ll = long long; using ull = unsigned long long; using pii = pair<int, int>; using pil = pair<int, ll>; using pli = pair<ll, int>; using pll = pair<ll, ll>; using ld = long double; template<typename T1, typename T2> bool chkmin(T1& x, T2 y) { return y < x ? (x = y, true) : false; } template<typename T1, typename T2> bool chkmax(T1& x, T2 y) { return y > x ? (x = y, true) : false; } void debug_out() { cerr << endl; } template<typename T1, typename... T2> void debug_out(T1 A, T2... B) { cerr << ' ' << A; debug_out(B...); } template<typename T> void mdebug_out(T* a, int n) { for (int i = 0; i < n; ++i) cerr << a[i] << ' '; cerr << endl; } #ifdef LOCAL #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n) #else #define debug(...) 1337 #define mdebug(a, n) 1337 #endif template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) { for (auto& x : v) stream << x << ' '; return stream; } template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) { return stream << p.first << ' ' << p.second; } const int INF32 = 0x3f3f3f3f; const int maxN = 750005; const int K = 20; ll cost[maxN]; int a[maxN]; namespace sgt { const int logN = 17; const int N = 1 << logN; struct Node { int mx; int sum[K]; // int fml[K], fmr[K]; int f[K][K]; Node() { mx = -1; memset(sum, 0, sizeof sum); // memset(fml, 0x3f, sizeof fml); // memset(fmr, 0x3f, sizeof fmr); memset(f, 0x3f, sizeof f); } Node(int x) { mx = x; for (int i = 0; i < K; ++i) { sum[i] = max(x, i); } // memset(fml, 0x3f, sizeof fml); // memset(fmr, 0x3f, sizeof fmr); // fml[x] = fmr[x] = x; memset(f, 0x3f, sizeof f); f[x][x] = x; } } t[2 * N]; Node operator * (const Node& lhs, const Node& rhs) { Node res; res.mx = max(lhs.mx, rhs.mx); for (int i = 0; i < K; ++i) res.sum[i] = lhs.sum[i] + rhs.sum[i]; // for (int i = 0; i < K; ++i) { // if (lhs.mx == res.mx && rhs.mx <= i) { // chkmin(res.fml[i], lhs.fml[i] + rhs.sum[i]); // } // chkmin(res.fml[i], rhs.fml[i] + lhs.sum[rhs.mx]); // if (rhs.mx == res.mx && lhs.mx <= i) { // chkmin(res.fmr[i], rhs.fmr[i] + lhs.sum[i]); // } // chkmin(res.fmr[i], lhs.fmr[i] + rhs.sum[lhs.mx]); // } for (int x = 0; x < K; ++x) for (int y = 0; y < K; ++y) { chkmin(res.f[x][max(y, rhs.mx)], lhs.f[x][y] + rhs.sum[y]); chkmin(res.f[max(x, lhs.mx)][y], lhs.sum[x] + rhs.f[x][y]); } return res; } void build(int v, int vl, int vr) { if (vl == vr) { t[v] = Node(a[vl]); return; } int vm = (vl + vr) >> 1; build(v << 1, vl, vm); build(v << 1 | 1, vm + 1, vr); t[v] = t[v << 1] * t[v << 1 | 1]; } Node gt(int v, int vl, int vr, int l, int r) { if (l > r || vr < l || r < vl) return Node(); if (l <= vl && vr <= r) return t[v]; int vm = (vl + vr) >> 1; return gt(v << 1, vl, vm, l, r) * gt(v << 1 | 1, vm + 1, vr, l, r); } } vector<ll> minimum_costs(vector<int> _a, vector<int> ql, vector<int> qr) { int n = _a.size(), Q = ql.size(); for (int i = 0; i < n; ++i) a[i] = _a[i] - 1; sgt::build(1, 0, n - 1); vector<ll> ans(Q); for (int j = 0; j < Q; ++j) { int l = ql[j], r = qr[j]; auto N = sgt::gt(1, 0, n - 1, l, r); int mn = INF32; for (int x = 0; x < K; ++x) for (int y = 0; y < K; ++y) chkmin(mn, N.f[x][y]); ans[j] = (r - l + 1) + mn;//min(*min_element(N.fml, N.fml + K), *min_element(N.fmr, N.fmr + K)); } return ans; } #ifdef LOCAL int read_int() { int x; if (scanf("%d", &x) != 1) { fprintf(stderr, "Error while reading input\n"); exit(1); } return x; } int32_t main() { #ifdef LOCAL freopen("in", "r", stdin); #endif ios::sync_with_stdio(0); cin.tie(0); int N = read_int(); int Q = read_int(); std::vector<int> H(N); for (int i = 0; i < N; ++i) { H[i] = read_int(); } std::vector<int> L(Q), R(Q); for (int j = 0; j < Q; ++j) { L[j] = read_int(); R[j] = read_int(); } std::vector<long long> C = minimum_costs(H, L, R); for (size_t j = 0; j < C.size(); ++j) { printf("%lld\n", C[j]); } return 0; return 0; } #endif
#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...