Submission #372492

#	Time	Username	Problem	Language	Result	Execution time	Memory
372492		denkendoemeer	Meetings (IOI18_meetings)	C++14	100 / 100	3329 ms	324516 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct lc
{
	int a,l,r;
	ll b,lazy;
	lc():a(0),l(0),r(0),b(0x3fffffffffffffffLL),lazy(0){}
};
pair<int,int>aint[1<<21];
lc lt[1<<21],rt[1<<21];
vector<long long>ans;
vector<tuple<int,int,int>>q[750001];
pair<int,int> calc(int st,int dr)
{
	pair<int,int>rez(-1,-1);
	for(st+=1<<20,dr+=1<<20;st<=dr;st>>=1,dr>>=1){
		if (st&1)
            rez=max(rez,aint[st++]);
		if (~dr&1)
            rez=max(rez,aint[dr--]);
	}
	return rez;
}
void push(lc *aint,int nod,int st,int dr)
{
	if (aint[nod].lazy){
		aint[nod].b+=aint[nod].lazy;
		if (st<dr){
			aint[2*nod].lazy+=aint[nod].lazy;
			aint[2*nod+1].lazy+=aint[nod].lazy;
		}
		aint[nod].lazy=0;
	}
}
int semn(ll x)
{
    if (x<0)
        return -1;
    return x>0;
}
void addlin(lc *aint,int l,int r,int a,long long b,int nod=1,int st=0,int dr=(1<<20)-1)
{
	int mij=(st+dr)/2;
	push(aint,nod,st,dr);
	if (r<l || r<st || dr<l)
        return;
	if (l<=st && dr<=r){
		ll st2=1LL*a*st+b,mij2=1LL*a*mij+b,dr2=1LL*a*dr+b,st3=1LL*aint[nod].a*st+aint[nod].b,mij3=1LL*aint[nod].a*mij+aint[nod].b,dr3=1LL*aint[nod].a*dr+aint[nod].b;
		if (mij2<mij3){
			swap(aint[nod].a,a);
            swap(aint[nod].b,b);
			swap(st3,st2);
			swap(mij3,mij2);
			swap(dr3,dr2);
		}
		if (st3<=st2 && dr3<=dr2)
            return;
		if (semn(st2-st3)*semn(mij2-mij3)<0 || mij2==mij3 && st2<st3)
            addlin(aint,l,r,a,b,2*nod,st,mij);
		else
            addlin(aint,l,r,a,b,2*nod+1,mij+1,dr);
		return;
	}
	addlin(aint,l,r,a,b,2*nod,st,mij);
	addlin(aint,l,r,a,b,2*nod+1,mij+1,dr);
}
void add(lc *aint,int l,int r,ll val,int nod=1,int st=0,int dr=(1<<20)-1)
{
	int mij=(st+dr)/2;
	push(aint,nod,st,dr);
	if (r<l || r<st || dr<l)
        return;
	if (l<=st && dr<=r){
		aint[nod].lazy=val;
		push(aint,nod,st,dr);
		return;
	}
	add(aint,l,r,val,2*nod,st,mij);
	add(aint,l,r,val,2*nod+1,mij+1,dr);
}
long long calcy(lc *aint,int poz,int nod=1,int st=0,int dr=(1<<20)-1)
{
	int mij=(st+dr)/2;
	push(aint,nod,st,dr);
	if (st==dr)
        return 1LL*aint[nod].a*poz+aint[nod].b;
	return min(poz<=mij?calcy(aint,poz,2*nod,st,mij):calcy(aint,poz,2*nod+1,mij+1,dr),1LL*aint[nod].a*poz+aint[nod].b);
}
void solve(int st,int dr)
{
	if (st>dr)
        return;
	auto [a,b]=calc(st,dr);
	solve(st,b-1);
	solve(b+1,dr);
	for(auto [l,r,i]:q[b])
        ans[i]=min(calcy(lt,l)+(r-b+1LL)*a,calcy(rt,r)+(b-l+1LL)*a);
	add(lt,st,b-1,(dr-b+1LL)*a);
	if (b<dr)
        addlin(lt,st,b,-a,calcy(lt,b+1)+a*(b+1LL));
    else
        addlin(lt,st,b,-a,a*(b+1LL));
	add(rt,b+1,dr,(b-st+1LL)*a);
	if (st<b)
        addlin(rt,b,dr,a,calcy(rt,b-1)+a*(1LL-b));
    else
        addlin(rt,b,dr,a,a*(1LL-b));
}
vector<long long> minimum_costs(vector<int>H,vector<int>L,vector<int>R)
{
	int n=H.size(),m=L.size();
	ans.resize(m);
	int i;
	for(i=0;i<n;i++)
        aint[(1<<20)+i+1]={H[i],i+1};
	for(i=(1<<20);--i;)
        aint[i]=max(aint[2*i],aint[2*i+1]);
	for(i=0;i<m;i++){
		if (++L[i]<++R[i])
            q[calc(L[i],R[i]).second].emplace_back(L[i],R[i],i);
		else
            ans[i]=H[L[i]-1];
	}
	solve(1,n);
	return ans;
}

Compilation message (stderr)

meetings.cpp: In function 'void addlin(lc*, int, int, int, long long int, int, int, int)':
meetings.cpp:60:53: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   60 |   if (semn(st2-st3)*semn(mij2-mij3)<0 || mij2==mij3 && st2<st3)
      |                                          ~~~~~~~~~~~^~~~~~~~~~
meetings.cpp: In function 'void solve(int, int)':
meetings.cpp:95:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   95 |  auto [a,b]=calc(st,dr);
      |       ^
meetings.cpp:98:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   98 |  for(auto [l,r,i]:q[b])
      |           ^
meetings.cpp:103:5: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
  103 |     else
      |     ^~~~
meetings.cpp:105:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
  105 |  add(rt,b+1,dr,(b-st+1LL)*a);
      |  ^~~

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