제출 #360899

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
360899		arnold518	모임들 (IOI18_meetings)	C++14	19 / 100	5590 ms	5988 KiB

meetings

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 75e4;
const ll INF = 1e18;

struct Data
{
	int l, r, p;
};

int N, Q;
ll A[MAXN+10];
Data B[MAXN+10];
ll ans[MAXN+10];

ll val[MAXN+10];

vector<ll> minimum_costs(vector<int> _H, vector<int> _L, vector<int> _R)
{
	N=_H.size(); Q=_L.size();
	for(int i=1; i<=N; i++) A[i]=_H[i-1];
	for(int i=1; i<=Q; i++) B[i]={_L[i-1]+1, _R[i-1]+1, i};

	for(int i=1; i<=Q; i++)
	{
		for(int j=B[i].l; j<=B[i].r; j++) val[j]=-A[j];

		ll t=0;
		vector<int> S;
		S.push_back(B[i].l-1);
		for(int j=B[i].l; j<=B[i].r; j++)
		{
			while(S.size()>1 && A[S.back()]<=A[j])
			{
				t-=A[S[S.size()-1]]*(S[S.size()-1]-S[S.size()-2]);
				S.pop_back();
			}
			t+=A[j]*(j-S.back());
			S.push_back(j);
			val[j]+=t;
		}

		t=0;
		S.clear();
		S.push_back(B[i].r+1);
		for(int j=B[i].r; j>=B[i].l; j--)
		{
			while(S.size()>1 && A[S.back()]<=A[j])
			{
				t-=A[S[S.size()-1]]*(S[S.size()-2]-S[S.size()-1]);
				S.pop_back();
			}
			t+=A[j]*(S.back()-j);
			S.push_back(j);
			val[j]+=t;
		}

		ans[i]=INF;
		//for(int j=B[i].l; j<=B[i].r; j++) printf("%lld ", val[j]); printf("\n");
		for(int j=B[i].l; j<=B[i].r; j++) ans[i]=min(ans[i], val[j]);

	}



	vector<ll> ret;
	for(int i=1; i<=Q; i++) ret.push_back(ans[i]);
	return ret;
}

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