Submission #159115

#	Time	Username	Problem	Language	Result	Execution time	Memory
159115		kig9981	Meetings (IOI18_meetings)	C++17	100 / 100	3257 ms	324328 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;

struct lichao
{
	int A, l, r;
	long long B, lazy;
	lichao() : A(0), l(0), r(0), B(0x3fffffffffffffffLL), lazy(0) {}
};

const int SZ=1<<20;
pair<int,int> Mtree[2*SZ];
lichao ltree[2*SZ], rtree[2*SZ];
vector<long long> res;
vector<tuple<int,int,int>> Q[750001];

pair<int,int> get_max(int s, int e)
{
	pair<int,int> ret(-1,-1);
	for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
		if(s&1) ret=max(ret,Mtree[s++]);
		if(~e&1) ret=max(ret,Mtree[e--]);
	}
	return ret;
}

void lazy_propagation(lichao *tree, int bit, int s, int e)
{
	if(tree[bit].lazy) {
		tree[bit].B+=tree[bit].lazy;
		if(s<e) {
			tree[2*bit].lazy+=tree[bit].lazy;
			tree[2*bit+1].lazy+=tree[bit].lazy;
		}
		tree[bit].lazy=0;
	}
}

int get_sign(long long a)
{
	return a<0 ? -1:a>0;
}

void add_line(lichao *tree, int n1, int n2, int A, long long B, int bit=1, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	lazy_propagation(tree,bit,s,e);
	if(n2<n1 || n2<s || e<n1) return;
	if(n1<=s && e<=n2) {
		int &pA=tree[bit].A;
		long long &pB=tree[bit].B, ys=1LL*A*s+B, ym=1LL*A*m+B, ye=1LL*A*e+B, pys=1LL*pA*s+pB, pym=1LL*pA*m+pB, pye=1LL*pA*e+pB;
		if(ym<pym) {
			swap(pA,A); swap(pB,B);
			swap(pys,ys); swap(pym,ym); swap(pye,ye);
		}
		if(pys<=ys && pye<=ye) return;
		if(get_sign(ys-pys)*get_sign(ym-pym)<0 || ym==pym && ys<pys) add_line(tree,n1,n2,A,B,2*bit,s,m);
		else add_line(tree,n1,n2,A,B,2*bit+1,m+1,e);
		return;
	}
	add_line(tree,n1,n2,A,B,2*bit,s,m);
	add_line(tree,n1,n2,A,B,2*bit+1,m+1,e);
}

void add_tree(lichao *tree, int n1, int n2, long long v, int bit=1, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	lazy_propagation(tree,bit,s,e);
	if(n2<n1 || n2<s || e<n1) return;
	if(n1<=s && e<=n2) {
		tree[bit].lazy=v;
		lazy_propagation(tree,bit,s,e);
		return;
	}
	add_tree(tree,n1,n2,v,2*bit,s,m);
	add_tree(tree,n1,n2,v,2*bit+1,m+1,e);
}

long long get_y(lichao *tree, int x, int bit=1, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	lazy_propagation(tree,bit,s,e);
	if(s==e) return 1LL*tree[bit].A*x+tree[bit].B;
	return min(x<=m ? get_y(tree,x,2*bit,s,m):get_y(tree,x,2*bit+1,m+1,e),1LL*tree[bit].A*x+tree[bit].B);
}

void solve(int s, int e)
{
	if(s>e) return;
	auto[M,m]=get_max(s,e);
	solve(s,m-1);
	solve(m+1,e);
	for(auto[l,r,i]: Q[m]) res[i]=min(get_y(ltree,l)+(r-m+1LL)*M,get_y(rtree,r)+(m-l+1LL)*M);
	add_tree(ltree,s,m-1,(e-m+1LL)*M);
	add_line(ltree,s,m,-M,(m<e ? get_y(ltree,m+1):0)+M*(m+1LL));
	add_tree(rtree,m+1,e,(m-s+1LL)*M);
	add_line(rtree,m,e,M,(s<m ? get_y(rtree,m-1):0)+M*(1LL-m));
}

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R)
{
	int N=H.size(), M=L.size();
	res.resize(M);
	for(int i=0;i<N;i++) Mtree[SZ+i+1]={H[i],i+1};
	for(int i=SZ;--i;) Mtree[i]=max(Mtree[2*i],Mtree[2*i+1]);
	for(int i=0;i<M;i++) {
		if(++L[i]<++R[i]) Q[get_max(L[i],R[i]).second].emplace_back(L[i],R[i],i);
		else res[i]=H[L[i]-1];
	}
	solve(1,N);
	return res;
}

Compilation message (stderr)

meetings.cpp: In function 'void add_line(lichao*, int, int, int, long long int, int, int, int)':
meetings.cpp:59:53: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if(get_sign(ys-pys)*get_sign(ym-pym)<0 || ym==pym && ys<pys) add_line(tree,n1,n2,A,B,2*bit,s,m);
                                             ~~~~~~~~^~~~~~~~~

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