oj.uz

Submission #592946

# Submission time Handle Problem Language Result Execution time Memory
592946 2022-07-09T21:38:20 Z Bobaa Meetings (IOI18_meetings) C++17
100 / 100
 2300 ms 255888 KB 
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
 
pair<ll, ll> sc[1<<20];
vector<int> ls, le, nxt, cnt;
vector<int> H, L, R;
vector<ll> ans, pl;
vector<vector<int>> qu;
vector<array<int, 2>> ct;
set<int> sv;
pair<int, int> st[1<<21];
int vis[1<<20];
 
ll 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[u]);
	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<ll> 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=0; i<(int)L.size(); i++) qu[getmx(L[i], R[i])].emplace_back(i);
		dfs(rt);
		reverse(H.begin(), H.end());
		for (int i=0; i<(int)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

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:101: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]
  101 |   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
      |            ^~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16724 KB Output is correct
2 Correct 18 ms 17132 KB Output is correct
3 Correct 15 ms 17136 KB Output is correct
4 Correct 14 ms 17108 KB Output is correct
5 Correct 14 ms 17108 KB Output is correct
6 Correct 14 ms 17348 KB Output is correct
7 Correct 14 ms 17096 KB Output is correct
8 Correct 14 ms 17392 KB Output is correct
9 Correct 13 ms 17288 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16724 KB Output is correct
2 Correct 18 ms 17132 KB Output is correct
3 Correct 15 ms 17136 KB Output is correct
4 Correct 14 ms 17108 KB Output is correct
5 Correct 14 ms 17108 KB Output is correct
6 Correct 14 ms 17348 KB Output is correct
7 Correct 14 ms 17096 KB Output is correct
8 Correct 14 ms 17392 KB Output is correct
9 Correct 13 ms 17288 KB Output is correct
10 Correct 23 ms 17744 KB Output is correct
11 Correct 19 ms 17740 KB Output is correct
12 Correct 24 ms 17736 KB Output is correct
13 Correct 19 ms 17864 KB Output is correct
14 Correct 21 ms 18124 KB Output is correct
15 Correct 19 ms 17752 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16696 KB Output is correct
2 Correct 49 ms 21312 KB Output is correct
3 Correct 183 ms 43280 KB Output is correct
4 Correct 164 ms 36932 KB Output is correct
5 Correct 149 ms 44216 KB Output is correct
6 Correct 156 ms 45224 KB Output is correct
7 Correct 180 ms 46392 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16696 KB Output is correct
2 Correct 49 ms 21312 KB Output is correct
3 Correct 183 ms 43280 KB Output is correct
4 Correct 164 ms 36932 KB Output is correct
5 Correct 149 ms 44216 KB Output is correct
6 Correct 156 ms 45224 KB Output is correct
7 Correct 180 ms 46392 KB Output is correct
8 Correct 176 ms 37384 KB Output is correct
9 Correct 153 ms 37308 KB Output is correct
10 Correct 165 ms 37500 KB Output is correct
11 Correct 172 ms 36724 KB Output is correct
12 Correct 151 ms 36516 KB Output is correct
13 Correct 167 ms 36972 KB Output is correct
14 Correct 170 ms 43648 KB Output is correct
15 Correct 153 ms 36076 KB Output is correct
16 Correct 169 ms 43724 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16724 KB Output is correct
2 Correct 18 ms 17132 KB Output is correct
3 Correct 15 ms 17136 KB Output is correct
4 Correct 14 ms 17108 KB Output is correct
5 Correct 14 ms 17108 KB Output is correct
6 Correct 14 ms 17348 KB Output is correct
7 Correct 14 ms 17096 KB Output is correct
8 Correct 14 ms 17392 KB Output is correct
9 Correct 13 ms 17288 KB Output is correct
10 Correct 23 ms 17744 KB Output is correct
11 Correct 19 ms 17740 KB Output is correct
12 Correct 24 ms 17736 KB Output is correct
13 Correct 19 ms 17864 KB Output is correct
14 Correct 21 ms 18124 KB Output is correct
15 Correct 19 ms 17752 KB Output is correct
16 Correct 12 ms 16696 KB Output is correct
17 Correct 49 ms 21312 KB Output is correct
18 Correct 183 ms 43280 KB Output is correct
19 Correct 164 ms 36932 KB Output is correct
20 Correct 149 ms 44216 KB Output is correct
21 Correct 156 ms 45224 KB Output is correct
22 Correct 180 ms 46392 KB Output is correct
23 Correct 176 ms 37384 KB Output is correct
24 Correct 153 ms 37308 KB Output is correct
25 Correct 165 ms 37500 KB Output is correct
26 Correct 172 ms 36724 KB Output is correct
27 Correct 151 ms 36516 KB Output is correct
28 Correct 167 ms 36972 KB Output is correct
29 Correct 170 ms 43648 KB Output is correct
30 Correct 153 ms 36076 KB Output is correct
31 Correct 169 ms 43724 KB Output is correct
32 Correct 1453 ms 162052 KB Output is correct
33 Correct 1189 ms 158056 KB Output is correct
34 Correct 1337 ms 159440 KB Output is correct
35 Correct 1653 ms 163752 KB Output is correct
36 Correct 1242 ms 164576 KB Output is correct
37 Correct 1346 ms 165560 KB Output is correct
38 Correct 1785 ms 214708 KB Output is correct
39 Correct 2300 ms 214720 KB Output is correct
40 Correct 1610 ms 169548 KB Output is correct
41 Correct 1794 ms 255888 KB Output is correct
42 Correct 2219 ms 254668 KB Output is correct
43 Correct 2271 ms 254660 KB Output is correct
44 Correct 2299 ms 214712 KB Output is correct