Submission #592944

#	Time	Username	Problem	Language	Result	Execution time	Memory
592944		Bobaa	Meetings (IOI18_meetings)	C++17	0 / 100	12 ms	16724 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std; 

pair<long long, long long> sc[1 << 20]; 
vector<int> ls, le, nxt, cnt; 
vector<int> H, L, R; 
vector<long long> ans, pl; 
vector<vector<int>> qu; 
vector<array<int, 2>> ct; 
set<int> sv; 
pair<int, int> st[1 << 21]; 
int vis[1 << 20]; 

long long getv(int i, int x) {
	return sc[i].first * x  + sc[i].second; 
}

void cal(int u, int l) {
	for (int i : qu[u]) {
		auto it = --sv.upper_bound(R[i]); 
		ans[i] = min(ans[i], getv(max(ls[u], min(le[u], *it)), R[i]) + pl[u] - 1ll * H[u] * (L[i] - l)); 
	}
}

void dfs(int u) {
	if (u == -1) return; 
	vis[u] = 1; 
	auto [l, r] = ct[u]; 
	dfs(l); 
	dfs(r); 
	if (l != -1) {
		ls[u] = ls[l]; 
		pl[u] = pl[l]; 
		cnt[u] += cnt[l]; 
	}
	sc[u] = {H[u], (l != -1 ? getv(le[l], u - 1) + pl[u] : 0) + H[u] - 1ll * u * H[u] - pl[u]}; 
	if (r == -1) {
		for (int i : qu[u]) ans[i] = min(ans[i], 1ll * (R[i] - L[i] + 1) * H[u]); 
		return; 
	}
	pl[r] += 1ll * (u - ls[u] + 1) * H[u]; 
	swap(ls[r], ls[u]); 
	swap(le[r], le[u]); 
	swap(pl[r], pl[r]); 
	cal(u, ls[r]); 
	swap(ls[r], ls[u]); 
	swap(le[r], le[u]);
	swap(pl[r], pl[u]);
	while (nxt[u] <= le[r]) {
		if (getv(nxt[u], nxt[nxt[u]] - 1) + pl[r] >= getv(u, nxt[nxt[u]] - 1) + pl[u]) {
			sv.erase(nxt[u]); 
			nxt[u] = nxt[nxt[u]];
			cnt[r]--;
		}
		else if (getv(nxt[u], nxt[u]) + pl[r] < getv(u, nxt[u]) + pl[u]) break; 
		else {
			sv.erase(nxt[u]); 
			int s = nxt[u], e = nxt[nxt[u]] - 1; 
			while (s < e) {
				int m = (s + e + 1) / 2; 
				if (getv(nxt[u], m) + pl[r] >= getv(u, m) + pl[u]) s = m; 
				else e = m - 1; 
			}
			sc[s + 1] = sc[nxt[u]]; 
			nxt[s + 1] = nxt[nxt[u]]; 
			if (nxt[u] == le[r]) le[r] = s + 1; 
			sv.emplace(s + 1); 
			nxt[u] = s + 1; 
			break;
		}
	}
	if (cnt[u] < cnt[r]) {
		for (int i = ls[u]; i <= u; i = nxt[i]) sc[i].second += pl[u] - pl[r]; 
		pl[u] = pl[r]; 
	}
	else for (int i = nxt[u]; i <= le[r]; i = nxt[i]) sc[i].second += pl[r] - pl[u]; 
	if (nxt[u] <= le[r]) le[u] = le[r]; 
	cnt[u] += cnt[r]; 
}

vector<long long> minimum_costs(vector<int> hh, vector<int> ll, vector<int> rr) {
	int n = hh.size(); 
	H = hh; 
	L = ll; 
	R = rr; 
	ans.resize(L.size(), 1e18); 
	ct.resize(n, {-1, 1}); 
	qu.resize(n); 
	pl.resize(n); 
	ls.resize(n); 
	le = nxt = cnt = ls; 
	for (int &i : nxt) i++; 
	vector<int> pr(n), lc(n, -1), rc(n, -1); 
	int rt = 0; 
	for (int i = 1, lst; i < n; i++) {
		lst = i - 1; 
		while (H[lst] < H[i] && lst != rt) lst = pr[lst]; 
		if (H[lst] < H[i]) {
			pr[rt] = i; 
			lc[i] = rt; 
			rt = i; 
		}
		else if (rc[lst] == -1) {
			rc[lst] = i; 
			pr[i] = lst; 
		}
		else {
			pr[rc[lst]] = i; 
			lc[i] = rc[lst]; 
			rc[lst] = i; 
			pr[i] = lst; 
		}
	}
	for (int i = 0; i < n; i++) ct[i] = {lc[i], rc[i]}; 
	for (int tr = 0; tr < 2; tr++) {
		sv.clear(); 
		for (int i = 0; i < n; i++) {
			sv.emplace(i); 
			qu[i].clear(); 
			pl[i] = 0; 
			ls[i] = i; 
			cnt[i] = 1; 
		}
		le = nxt = ls; 
		for (int &i : nxt) i++; 
		memset(st, 0, sizeof(st)); 
		for (int i = 0; i < n; i++) st[i + (1 << 20)] = {H[i], i * (tr ? 1 : -1)}; 
		for (int i = (1 << 20) - 1; i; i--) st[i] = max(st[i * 2], st[i * 2 + 1]); 
		auto getmx = [&](int l, int r) {
			l += (1 << 20); 
			r += (1 << 20); 
			pair<int, int> rt(0, 0); 
			while (l <= r) {
				if (l % 2) {
					rt = max(rt, st[l]); 
					l++; 
				}
				if (r % 2 == 0) {
					rt = max(rt, st[r]); 
					r--; 
				}
				l /= 2; 
				r /= 2; 
			}
			return rt.second * (tr ? 1 : -1); 
		};
		for (int i = 1; i < L.size(); i++) qu[getmx(L[i], R[i])].emplace_back(i); 
		dfs(rt); 
		reverse(H.begin(), H.end()); 
		for (int i = 0; i < L.size(); i++) tie(L[i], R[i]) = make_pair(n - 1 - R[i], n - 1 - L[i]); 
		rt = n - 1 - rt; 
		for (auto &[l, r] : ct) tie(l, r) = make_pair(r == -1 ? -1 : n - 1 - r, l == -1 ? -1 : n - 1 - l); 
		reverse(ct.begin(), ct.end()); 
	}
	return ans; 
}

Compilation message (stderr)

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:127:27: warning: 'void* memset(void*, int, size_t)' clearing an object of type 'struct std::pair<int, int>' with no trivial copy-assignment; use assignment instead [-Wclass-memaccess]
  127 |   memset(st, 0, sizeof(st));
      |                           ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from meetings.h:3,
                 from meetings.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<int, int>' declared here
  211 |     struct pair
      |            ^~~~
meetings.cpp:148:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |   for (int i = 1; i < L.size(); i++) qu[getmx(L[i], R[i])].emplace_back(i);
      |                   ~~^~~~~~~~~~
meetings.cpp:151:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |   for (int i = 0; i < L.size(); i++) tie(L[i], R[i]) = make_pair(n - 1 - R[i], n - 1 - L[i]);
      |                   ~~^~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40