Submission #122051

#	Time	Username	Problem	Language	Result	Execution time	Memory
122051		SirCeness	Meetings (IOI18_meetings)	C++14	0 / 100	57 ms	1820 KiB

meetings

#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;

int n, q;
vector<int> arr;
int st[400005][3];

void stc(int node, int l, int r){
	if (l == r) st[node][0] = st[node][1] = st[node][2] = (arr[l] == 1);
	else {
		int m = (l+r)/2;
		stc(node*2, l, m);
		stc(node*2+1, m+1, r);
		
		st[node][0] = max(max(st[node*2][0], st[node*2+1][0]), st[node*2][2] + st[node*2+1][1]);
		
		if (st[node*2][1] == (r-l+1)/2) st[node][1] = (r-l+1)/2 + st[node*2+1][1];
		else st[node][1] = st[node*2][1];
		
		if (st[node*2+1][2] == (r-l+1)/2) st[node][2] = st[node*2][2] + (r-l+1)/2;
		else st[node][2] = st[node*2+1][2];
	}
}

int stq(int node, int l, int r, int sl, int sr, int mode){
	if (sl <= l && r <= sr){
		return st[node][mode];
	} else if (r < sl || sr < l){
		return 0;
	} else {
		int m = (l+r)/2;
		
		if (mode == 0){
			int ans1 = stq(node*2, l, m, sl, sr, 0);
			int ans2 = stq(node*2+1, m+1, r, sl, sr, 0);
			int ans3 = stq(node*2, l, m, sl, sr, 2) + stq(node*2+1, m+1, r, sl, sr, 1);
			return max(max(ans1, ans2), ans3);
		} else if (mode == 1){
			int ans1 = 0, ans2 = 0;
			ans1 = stq(node*2, l, m, sl, sr, 1);
			if (ans1 == (m-(max(sl, l))+1)) ans2 = ans1 + stq(node*2+1, m+1, r, sl, sr, 1);
			return max(ans1, ans2);
		} else if (mode == 2){
			int ans1 = 0, ans2 = 0;
			ans1 = stq(node*2+1, m+1, r, sl, sr, 2);
			if (ans1 == min(sr, r)-m) ans2 = ans1 + stq(node*2, l, m, sl, sr, 2);
			return max(ans1, ans2);
		} else assert(0);
	}
}

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
	n = H.size();
	q = L.size();
	arr = H;
	vector<ll> ans(q);
	stc(1, 0, n-1);
	for (int i = 0; i < q; i++){
		ans[i] = (R[i]-L[i]+1)*2-stq(1, 0, n-1, L[i], R[i], 0);
	}
	return ans;
}

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