제출 #970869

#제출 시각아이디문제언어결과실행 시간메모리
970869nguyentunglam모임들 (IOI18_meetings)C++17
0 / 100
37 ms60372 KiB
#include "meetings.h" #include<bits/stdc++.h> using namespace std; const int N = 750'000 + 10; int pre[N], nxt[N], lg[N], sp[20][N]; long long h[N]; vector<int> query[N]; struct IT { pair<long long, long long> lazy[N << 2]; void gather(pair<long long, long long> &a, pair<long long, long long> &b) { if (b.first != -1e9) a = b; else a.second += b.second; } void push(int s, int l, int r) { if (l == r) return; gather(lazy[s << 1], lazy[s]); gather(lazy[s << 1 | 1], lazy[s]); lazy[s] = make_pair(-1e9, 0); } void up(int s, int l, int r, int from, int to, pair<long long, long long> val) { push(s, l, r); if (l > to || r < from) return; if (from <= l && r <= to) { gather(lazy[s], val); return; } int mid = l + r >> 1; up(s << 1, l, mid, from, to, val); up(s << 1 | 1, mid + 1, r, from, to, val); } pair<long long, long long> get(int s, int l, int r, int pos) { push(s, l, r); if (l == r) return lazy[s]; int mid = l + r >> 1; if (pos <= mid) return get(s << 1, l, mid, pos); return get(s << 1 | 1, mid + 1, r, pos); } } prefix, suffix; int best(int x, int y) { if (h[x] == h[y]) return x < y ? x : y; return h[x] > h[y] ? x : y; } int getmax (int l, int r) { int k = lg[r - l + 1]; return best(sp[k][l], sp[k][r - (1 << k) + 1]); } std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) { int q = L.size(); int n = H.size(); for(int i = 0; i < n; i++) sp[0][i] = i, h[i] = H[i]; for(int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1; for(int j = 1; j <= lg[n]; j++) for(int i = 0; i + (1 << j) - 1 < n; i++) { sp[j][i] = best(sp[j - 1][i], sp[j - 1][i + (1 << j - 1)]); } vector<long long> ans(q); for(int i = 0; i < q; i++) { ans[i] = 1e18; if (L[i] == R[i]) ans[i] = h[i]; else { int x = getmax(L[i], R[i]); query[x].emplace_back(i); } } vector<int> order(n); for(int i = 0; i < n; i++) order[i] = i; sort(order.begin(), order.end(), [] (const int &x, const int &y) { if (h[x] == h[y]) return x > y; return h[x] < h[y]; }); for(int i = 1; i <= 4 * n; i++) prefix.lazy[i] = suffix.lazy[i] = make_pair(-1e9, 0); auto get_prefix = [&] (int pos) { pair<long long, long long> tmp = prefix.get(1, 0, n - 1, pos); if (tmp.first == -1e9) return tmp.second; return tmp.first * pos + tmp.second; }; auto get_suffix = [&] (int pos) { pair<long long, long long> tmp = suffix.get(1, 0, n - 1, pos); if (tmp.first == -1e9) return tmp.second; return tmp.first * pos + tmp.second; }; for(int i = 0; i < n; i++) pre[i] = i - 1, nxt[i] = i + 1; for(int cur = 0; cur < n; cur++) { int v = order[cur]; int from = pre[v], to = nxt[v]; if (from > 0) nxt[from] = to; if (to < n) pre[to] = from; from++; to--; prefix.up(1, 0, n - 1, v, v, make_pair(0, get_prefix(v - 1) + h[v])); suffix.up(1, 0, n - 1, v, v, make_pair(0, get_suffix(v + 1) + h[v])); for(int &j : query[v]) { if (j == 0) { // cout << get_suffix(L[j]) + 1LL * (R[j] - v + 1) * h[v] << endl; } if (L[j] != v) ans[j] = min(ans[j], get_suffix(L[j]) + 1LL * (R[j] - v + 1) * h[v]); if (R[j] != v) ans[j] = min(ans[j], get_prefix(R[j]) + 1LL * (v - L[j] + 1) * h[v]); } long long left = get_prefix(v - 1); long long right = get_prefix(v + 1); // cout << from << " " << to << " " << v << endl; // cout << left << " " << right << endl; // cout << endl; int l, r, last; l = v + 1, r = from, last = v; while (l <= r) { int mid = l + r >> 1; if (left + h[v] * (mid - v + 1) <= h[v] * (v - from + 1) + get_prefix(mid)) { last = mid; l = mid + 1; } else r = mid - 1; } if (v + 1 <= last) prefix.up(1, 0, n - 1, v + 1, last, make_pair(h[v], left - h[v] * (v - 1))); if (last + 1 <= to) prefix.up(1, 0, n - 1, last + 1, to, make_pair(-1e9, h[v] * (v - from + 1))); l = from, r = v - 1, last = v; while (l <= r) { int mid = l + r >> 1; if (right + h[v] * (v - mid + 1) <= h[v] * (to - v + 1) + get_suffix(mid)) { last = mid; r = mid - 1; } else l = mid + 1; } if (last <= v - 1) suffix.up(1, 0, n - 1, last, v - 1, make_pair(-h[v], right + h[v] * (v + 1))); if (from <= last - 1) suffix.up(1, 0, n - 1, from, last - 1, make_pair(-1e9, h[v] * (to - v + 1))); // if (v == 0) { //// prefix.up(1, 0, n - 1, 0, 0, make_pair(0, 2)); // cout << get_suffix(0) << endl; // } } return ans; } #ifdef ngu namespace { int read_int() { int x; if (scanf("%d", &x) != 1) { fprintf(stderr, "Error while reading input\n"); exit(1); } return x; } } // namespace int main() { freopen ("task.inp", "r", stdin); freopen ("task.out", "w", stdout); 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; } #endif // ngu

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

meetings.cpp: In member function 'void IT::up(int, int, int, int, int, std::pair<long long int, long long int>)':
meetings.cpp:35:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |   int mid = l + r >> 1;
      |             ~~^~~
meetings.cpp: In member function 'std::pair<long long int, long long int> IT::get(int, int, int, int)':
meetings.cpp:43:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |   int mid = l + r >> 1;
      |             ~~^~~
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:69:57: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   69 |     sp[j][i] = best(sp[j - 1][i], sp[j - 1][i + (1 << j - 1)]);
      |                                                       ~~^~~
meetings.cpp:139:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  139 |       int mid = l + r >> 1;
      |                 ~~^~~
meetings.cpp:152:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  152 |       int mid = l + r >> 1;
      |                 ~~^~~
#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...