제출 #131076

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
131076		tmwilliamlin168	모임들 (IOI18_meetings)	C++14	0 / 100	40 ms	4572 KiB

meetings

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

#define ll long long

const int mxN=7.5e5;
int n, q;
vector<int> h;

struct ct {
	array<int, 2> st[20][mxN];
	int c[mxN][2];
	ll ans[mxN];

	array<int, 2> qry(int l, int r) {
		int k=31-__builtin_clz(r-l+1);
		return max(st[k][l], st[k][r-(1<<k)+1]);
	}

	int bld(int l=0, int r=n-1, int p=-1) {
		if(l>r)
			return -1;
		int u=qry(l, r)[1];
		c[u][0]=bld(l, u-1, u);
		c[u][1]=bld(u+1, r, u);
		ans[u]=min((~c[u][0]?ans[c[u][0]]:0)+(r-u+1ll)*h[u], (~c[u][1]?ans[c[u][1]]:0)+(u-l+1ll)*h[u]);
		return u;
	}

	void init() {
		for(int i=0; i<n; ++i)
			st[0][i]={h[i], i};
		for(int k=1; k<20; ++k)
			for(int i=0; i<=n-(1<<k); ++i)
				st[k][i]=max(st[k-1][i], st[k-1][i+(1<<k-1)]);
		bld();
	}
} ct;

struct pch {
	int l[mxN], anc[mxN][20];
	ll c[mxN], a[mxN], b[mxN];

	ll ip(int i, int j) {
		return a[i]^a[j]?(b[j]-b[i])/(a[i]-a[j]):(b[i]<b[j]?1e18:-1e18);
	}

	void init(int x) {
		for(int i=0; i<n; ++i) {
			l[i]=i-1;
			while(~l[i]&&h[l[i]]<=h[i]-x)
				l[i]=l[l[i]];
			c[i]=h[i]*(i-l[i])+(~l[i]?c[l[i]]:0);
			a[i]=h[i];
			b[i]=(~ct.c[i][x]?ct.ans[ct.c[i][x]]:0)-(i-1ll)*h[i]+c[i];
		}
		for(int i=0; i<n; ++i) {
			//cout << i << endl;
			anc[i][0]=l[i];
			//if(~l[i]&&~anc[l[i]][0]&&(b[l[i]]-b[anc[l[i]][0]])/(a[anc[l[i]][0]]-a[l[i]])>(b[i]-b[l[i]])/(a[l[i]]-a[i])) {
			if(~l[i]&&~anc[l[i]][0]&&ip(anc[l[i]][0], l[i])>ip(l[i], i)) {
				for(int k=19; ~k; --k) {
					int j=anc[anc[i][0]][k];
					//if(~j&&~anc[j][0]&&(b[j]-b[anc[j][0]])/(a[anc[j][0]]-a[j])>(b[i]-b[j])/(a[j]-a[i]))
					if(~j&&~anc[j][0]&&ip(anc[j][0], j)>ip(j, i))
						anc[i][0]=j;
				}
				anc[i][0]=anc[anc[i][0]][0];
			}
			for(int k=1; k<20; ++k)
				anc[i][k]=~anc[i][k-1]?anc[anc[i][k-1]][k-1]:-1;
		}
	}

	ll qry(int s, int t) {
		if(s==t)
			return 0;
		int i=s;
		if(anc[i][0]>t&&a[anc[i][0]]*s+b[anc[i][0]]<a[i]*s+b[i]) {
			for(int k=19; ~k; --k) {
				int j=anc[i][k];
				if(~j&&~anc[j][0]&&anc[j][0]>t&&a[anc[j][0]]*s+b[anc[j][0]]<a[j]*s+b[j])
					i=j;
			}
			i=anc[i][0];
		}
		//cout << "f " << i << endl;
		//cout << a[i] << " " << b[i] << " " << c[i] << endl;
		ll ans=a[i]*s+b[i];
		for(int k=19; ~k; --k)
			if(~anc[i][k]&&anc[i][k]>t)
				i=anc[i][k];
		//cout << "s " << i << endl;
		return ans-c[i];
	}
} pl, pr;

vector<ll> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
	n=h.size(), q=l.size();
	::h=h;
	ct.init();
	//cout << "pli" << endl;
	pl.init(0);
	reverse(::h.begin(), ::h.end());
	reverse(ct.c, ct.c+n);
	//cout << "pri" << endl;
	pr.init(1);
	vector<ll> ans(q);
	for(int i=0; i<q; ++i) {
		int w=ct.qry(l[i], r[i])[1];
		//cout << "q " << l[i] << " " << r[i] << endl;
		//cout << w << endl;
		ll a1=pr.qry(n-1-l[i], n-1-w)+(r[i]-w+1ll)*h[w], a2=pl.qry(r[i], w)+(w-l[i]+1ll)*h[w];
		//cout << "prq " << a1 << " plq " << a2 << endl;
		ans[i]=min(a1, a2);
		//ans[i]=min(pr.qry(n-1-l[i], n-1-w)+(r[i]-w+1ll)*h[w], pl.qry(r[i], w)+(w-l[i]+1ll)*h[w]);
	}
	return ans;
}

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

meetings.cpp: In member function 'void ct::init()':
meetings.cpp:36:45: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
     st[k][i]=max(st[k-1][i], st[k-1][i+(1<<k-1)]);
                                            ~^~

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