Submission #360956

#	Time	Username	Problem	Language	Result	Execution time	Memory
360956		arnold518	Meetings (IOI18_meetings)	C++14	17 / 100	124 ms	8804 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];

int M;
pii C[MAXN+10];

struct SEG
{
	int tree[MAXN*4+10];
	void init(int node, int tl, int tr)
	{
		if(tl>tr) return;
		if(tl==tr)
		{
			tree[node]=C[tl].second-C[tl].first+1;
			return;
		}
		int mid=tl+tr>>1;
		init(node*2, tl, mid);
		init(node*2+1, mid+1, tr);
		tree[node]=max(tree[node*2], tree[node*2+1]);
	}
	int query(int node, int tl, int tr, int l, int r)
	{
		if(l>r) return 0;
		if(l<=tl && tr<=r) return tree[node];
		if(r<tl || tr<l) return 0;
		int mid=tl+tr>>1;
		return max(query(node*2, tl, mid, l, r), query(node*2+1, mid+1, tr, l, r));
	}
}seg;

vector<ll> ret;
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};

	A[0]=2; A[N+1]=2;

	vector<pii> V;
	for(int i=1; i<=N; i++)
	{
		if(A[i-1]==2 && A[i]==1) V.push_back({i, 0});
		if(A[i]==1 && A[i+1]==2) V.back().second=i;
	}

	M=V.size();
	for(int i=1; i<=M; i++) C[i]=V[i-1];
	C[0]=pii(0, 0); C[M+1]=pii(N+1, N+1);
	seg.init(1, 1, M);

	for(int i=1; i<=Q; i++)
	{
		int l, r;
		l=lower_bound(C+1, C+M+1, pii(B[i].l, 0), [&](const pii &p, const pii &q)
		{
			return p.first<q.first;
		})-C;
		r=upper_bound(C+1, C+M+1, pii(0, B[i].r), [&](const pii &p, const pii &q)
		{
			return p.second<q.second;
		})-C-1;

		int t=seg.query(1, 1, M, l, r);

		int tl=max(B[i].l, C[l-1].first), tr=min(B[i].r, C[l-1].second);
		t=max(t, tr-tl+1);

		tl=max(B[i].l, C[r+1].first), tr=min(B[i].r, C[r+1].second);
		t=max(t, tr-tl+1);

		ans[B[i].p]=2*(B[i].r-B[i].l+1)-t;
	}

/*
	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]);

	}
*/


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

Compilation message (stderr)

meetings.cpp: In member function 'void SEG::init(int, int, int)':
meetings.cpp:38:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |   int mid=tl+tr>>1;
      |           ~~^~~
meetings.cpp: In member function 'int SEG::query(int, int, int, int, int)':
meetings.cpp:48:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |   int mid=tl+tr>>1;
      |           ~~^~~

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