oj.uz

답안 #767972

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
767972 2023-06-27T10:32:06 Z marvinthang 모임들 (IOI18_meetings) C++17
100 / 100
 2146 ms 434776 KB 
/*************************************
*    author: marvinthang             *
*    created: 27.06.2023 11:42:33    *
*************************************/

#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
template <class A, class B> bool minimize(A &a, B b)  { if (a > b) { a = b; return true; } return false; }
template <class A, class B> bool maximize(A &a, B b)  { if (a < b) { a = b; return true; } return false; }

// end of template

const long long INF = 1e18;

struct Line {
	long long a, b;
	int len;
	Line(long long a = 0, long long b = 0, int len = 0): a(a), b(b), len(len) {}
	long long eval(int x) {
		return a * x + b;
	}
	friend print_op(Line) {
		return out << make_pair(u.a, u.b);
	}
};

vector <long long> minimum_costs(std::vector<int> H, vector <int> L, vector <int> R) {
	int N = H.size();
	int Q = L.size();

	stack <int> st;
	vector <int> par(N, -1);
	REP(i, N) {
		while (!st.empty() && H[st.top()] <= H[i]) st.pop();
		if (!st.empty()) par[i] = st.top();
		st.push(i);
	}
	while (!st.empty()) st.pop();
	REPD(i, N) {
		while (!st.empty() && H[st.top()] < H[i]) st.pop();
		if (!st.empty() && (par[i] == -1 || H[par[i]] > H[st.top()])) par[i] = st.top();
		st.push(i);
	}

	int root = find(ALL(par), -1) - par.begin();

	vector <vector <pair <int, int>>> max_val;
	max_val.push_back(vector<pair <int, int>>(N));
	REP(i, N) max_val[0][i] = make_pair(H[i], i);
	for (int k = 1; MASK(k) <= N; ++k) {
		vector <pair <int, int>> nxt;
		REP(i, N - MASK(k) + 1) nxt.push_back(max(max_val.back()[i], max_val.back()[i + MASK(k - 1)]));
		max_val.push_back(nxt);
	}
	auto get_max = [&] (int l, int r) {
		int h = __lg(r - l + 1);
		return max(max_val[h][l], max_val[h][r - MASK(h) + 1]);
	};

	vector <vector <int>> queriesAt(N);
	vector <long long> res(Q);
	REP(i, Q) {
		int ma = get_max(L[i], R[i]).se;
		res[i] = 1LL * (R[i] - L[i] + 1) * H[ma];
		queriesAt[ma].push_back(i);
	}

	REP(fl, 2) {
		vector <int> left_child(N, -1), right_child(N, -1);
		REP(i, N) if (~par[i]) (i < par[i] ? left_child[par[i]] : right_child[par[i]]) = i;
		map <int, Line> cost;
		vector <long long> lazy(N);
		vector <int> cnt(N);
		function <void(int, int, int)> dfs = [&] (int u, int prv, int nxt) {
			long long cost_left = 0;
			int l = left_child[u];
			if (~l) {
				dfs(l, prv, u - 1);
				lazy[u] = lazy[l];
				Line x = prev(cost.lower_bound(u))->se;
				cnt[u] = cnt[l];
				cost_left = x.eval(x.len - 1) + lazy[l];
			}
			cost[u] = Line(0, cost_left + H[u] - lazy[u], 1);
			++cnt[u];
			Line f(H[u], cost_left + H[u] + H[u]);

			int r = right_child[u];
			if (~r) {
				dfs(r, u + 1, nxt);
				for (int i: queriesAt[u]) {
					auto [x, l] = *prev(cost.upper_bound(R[i]));
					minimize(res[i], l.eval(R[i] - x) + lazy[r] + 1LL * (u - L[i] + 1) * H[u]);
				}
				lazy[r] += 1LL * (u - prv + 1) * H[u];
				for (auto it = cost.find(u + 1); it != cost.end() && it->fi <= nxt; ) {
					int v = it->fi;
					Line g = it->se;
					long long x = f.eval(f.len + g.len - 1);
					long long y = g.eval(g.len - 1) + lazy[r];
					it = cost.erase(it);
					--cnt[r];
					if (x <= y) {
						f.len += g.len;
					} else {
						int low = 0, high = g.len - 1;
						while (low <= high) {
							int m = low + high >> 1;
							if (f.eval(f.len + m) > g.eval(m) + lazy[r]) high = m - 1;
							else low = m + 1;
						}
						f.len += low;
						cost[v + low] = Line(g.a, g.b + g.a * low, g.len - low);
						++cnt[r];
						break;
					}
				}
				if (f.len) {
					f.b -= lazy[u];
					cost[u + 1] = f;
					++cnt[u];
				}
				if (cnt[u] <= cnt[r]) {
					for (auto it = cost.find(prv); it->fi <= u + f.len; ++it)
						it->se.b += lazy[u] - lazy[r];
					lazy[u] = lazy[r];
				} else {
					for (auto it = cost.find(u + f.len + 1); it != cost.end() && it->fi <= nxt; ++it)
						it->se.b += lazy[r] - lazy[u];
				}
				cnt[u] += cnt[r];
			}
		};
		dfs(root, 0, N - 1);
		root = N - root - 1;
		reverse(ALL(par));
		reverse(ALL(queriesAt));
		REP(i, N) if (~par[i]) par[i] = N - par[i] - 1;
		reverse(ALL(H));
		REP(i, Q) {
			L[i] = N - L[i] - 1;
			R[i] = N - R[i] - 1;
			swap(L[i], R[i]);
		}
	}
	return res;
}

#ifdef LOCAL
#include <cstdio>
#include <cstdlib>
#include <vector>
#include "meetings.h"

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() {
	file("meetings");
	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);
	cout << "answer:\n";
	for (size_t j = 0; j < C.size(); ++j) {
		printf("%lld\n", C[j]);
	}
	return 0;
}
#endif

Compilation message

meetings.cpp: In lambda function:
meetings.cpp:143:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  143 |        int m = low + high >> 1;
      |                ~~~~^~~~~~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 696 KB Output is correct
4 Correct 3 ms 692 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 3 ms 1332 KB Output is correct
9 Correct 2 ms 1076 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 696 KB Output is correct
4 Correct 3 ms 692 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 3 ms 1332 KB Output is correct
9 Correct 2 ms 1076 KB Output is correct
10 Correct 5 ms 1300 KB Output is correct
11 Correct 5 ms 1360 KB Output is correct
12 Correct 5 ms 1320 KB Output is correct
13 Correct 5 ms 1364 KB Output is correct
14 Correct 5 ms 2260 KB Output is correct
15 Correct 4 ms 1236 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 22 ms 5172 KB Output is correct
3 Correct 139 ms 42428 KB Output is correct
4 Correct 81 ms 23432 KB Output is correct
5 Correct 136 ms 44320 KB Output is correct
6 Correct 117 ms 43240 KB Output is correct
7 Correct 131 ms 49616 KB Output is correct

Subtask #4
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 22 ms 5172 KB Output is correct
3 Correct 139 ms 42428 KB Output is correct
4 Correct 81 ms 23432 KB Output is correct
5 Correct 136 ms 44320 KB Output is correct
6 Correct 117 ms 43240 KB Output is correct
7 Correct 131 ms 49616 KB Output is correct
8 Correct 111 ms 28296 KB Output is correct
9 Correct 105 ms 28168 KB Output is correct
10 Correct 112 ms 28304 KB Output is correct
11 Correct 97 ms 23476 KB Output is correct
12 Correct 94 ms 23404 KB Output is correct
13 Correct 101 ms 23572 KB Output is correct
14 Correct 143 ms 43448 KB Output is correct
15 Correct 71 ms 23008 KB Output is correct
16 Correct 138 ms 43704 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 696 KB Output is correct
4 Correct 3 ms 692 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 3 ms 1332 KB Output is correct
9 Correct 2 ms 1076 KB Output is correct
10 Correct 5 ms 1300 KB Output is correct
11 Correct 5 ms 1360 KB Output is correct
12 Correct 5 ms 1320 KB Output is correct
13 Correct 5 ms 1364 KB Output is correct
14 Correct 5 ms 2260 KB Output is correct
15 Correct 4 ms 1236 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 22 ms 5172 KB Output is correct
18 Correct 139 ms 42428 KB Output is correct
19 Correct 81 ms 23432 KB Output is correct
20 Correct 136 ms 44320 KB Output is correct
21 Correct 117 ms 43240 KB Output is correct
22 Correct 131 ms 49616 KB Output is correct
23 Correct 111 ms 28296 KB Output is correct
24 Correct 105 ms 28168 KB Output is correct
25 Correct 112 ms 28304 KB Output is correct
26 Correct 97 ms 23476 KB Output is correct
27 Correct 94 ms 23404 KB Output is correct
28 Correct 101 ms 23572 KB Output is correct
29 Correct 143 ms 43448 KB Output is correct
30 Correct 71 ms 23008 KB Output is correct
31 Correct 138 ms 43704 KB Output is correct
32 Correct 800 ms 191112 KB Output is correct
33 Correct 693 ms 190980 KB Output is correct
34 Correct 802 ms 192468 KB Output is correct
35 Correct 897 ms 196064 KB Output is correct
36 Correct 772 ms 195056 KB Output is correct
37 Correct 861 ms 196736 KB Output is correct
38 Correct 1756 ms 344952 KB Output is correct
39 Correct 1848 ms 344884 KB Output is correct
40 Correct 1164 ms 259516 KB Output is correct
41 Correct 1774 ms 433584 KB Output is correct
42 Correct 2146 ms 434776 KB Output is correct
43 Correct 2141 ms 434724 KB Output is correct
44 Correct 1976 ms 315152 KB Output is correct