제출 #295298

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
295298		Saboon	모임들 (IOI18_meetings)	C++17	36 / 100	1028 ms	9720 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18;
const int maxn = 1e5 + 10;
ll dp[maxn];

struct node{
	int pre = 0;
	int suf = 0;
	int sum = 0;
	bool fil = 0;
} seg[4*maxn];

node merge(node a, node b){
	node ret;
	ret.pre = a.pre + (a.fil * b.pre);
	ret.suf = b.suf + (b.fil * a.suf);
	ret.fil = (a.fil & b.fil);
	ret.sum = max({a.sum, b.sum, a.suf+b.pre});
	return ret;
}

node get(int id, int L, int R, int l, int r){
	if (l <= L and R <= r)
		return seg[id];
	int mid = (L + R) >> 1;
	if (r <= mid)
		return get(2*id+0, L, mid, l, r);
	if (mid <= l)
		return get(2*id+1, mid, R, l, r);
	return merge(get(2*id+0, L, mid, l, r), get(2*id+1, mid, R, l, r));
}

void add(int id, int L, int R, int idx){
	if (idx < L or R <= idx)
		return;
	if (L+1 == R){
		seg[id].pre = seg[id].suf = seg[id].sum = seg[id].fil = 1;
		return;
	}
	int mid = (L + R) >> 1;
	add(2*id+0, L, mid, idx);
	add(2*id+1, mid, R, idx);
	seg[id] = merge(seg[2*id+0], seg[2*id+1]);
}

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
	int n = H.size(), Q = L.size();
	if (n <= 5000 and Q <= 5000){
		vector<ll> C(Q);
		for (int j = 0; j < Q; j++){
			C[j] = inf;
			stack<pair<int,int>> S;
			ll Sum = 0;
			for (int i = L[j]; i <= R[j]; i++){
				int cnt = 1;
				while (!S.empty() and S.top().first <= H[i]){
					Sum -= 1LL*S.top().first*S.top().second;
					cnt += S.top().second;
					S.pop();
				}
				Sum += 1LL*H[i]*cnt;
				dp[i] = Sum;
				S.push({H[i],cnt});
			}
			while (!S.empty())
				S.pop();
			Sum = 0;
			for (int i = R[j]; i >= L[j]; i--){
				int cnt = 1;
				while (!S.empty() and S.top().first <= H[i]){
					Sum -= 1LL*S.top().first*S.top().second;
					cnt += S.top().second;
					S.pop();
				}
				Sum += 1LL*H[i]*cnt;
				C[j] = min(C[j], Sum+dp[i]-H[i]);
				S.push({H[i],cnt});
			}
		}
		return C;
	}
	if (*max_element(H.begin(),H.end()) <= 2){
		for (int i = 0; i < n; i++)
			if (H[i] == 1)
				add(1, 0, n, i);
		vector<ll> C(Q);
		for (int q = 0; q < Q; q++){
			int len = R[q]-L[q]+1;
			C[q] = 2*len - get(1, 0, n, L[q], R[q]+1).sum;
		}
		return C;
	}
}

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

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:96:1: warning: control reaches end of non-void function [-Wreturn-type]
   96 | }
      | ^

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