Submission #707584

#	Time	Username	Problem	Language	Result	Execution time	Memory
707584		AdamGS	Meetings (IOI18_meetings)	C++17	100 / 100	5308 ms	222980 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=75e4+7;
vector<pair<pair<int,int>,int>>V[LIM];
pair<ll,ll>tr[4*LIM][2], pytanie[4*LIM], T[LIM], zle={-1, -1};
set<pair<int,int>>S;
ll dodaj[4*LIM][2], ile[4*LIM], N=1;
void spl(int v, int k) {
	if(tr[v][k]!=zle) {
		tr[2*v][k]=tr[v][k];
		tr[2*v+1][k]={tr[v][k].st+ile[2*v]*tr[v][k].nd, tr[v][k].nd};
		tr[v][k]=zle;
		dodaj[2*v][k]=0;
		dodaj[2*v+1][k]=0;
	}
	if(dodaj[v][k]) {
		if(tr[2*v][k]!=zle) tr[2*v][k].st+=dodaj[v][k];
		else dodaj[2*v][k]+=dodaj[v][k];
		if(tr[2*v+1][k]!=zle) tr[2*v+1][k].st+=dodaj[v][k];
		else dodaj[2*v+1][k]+=dodaj[v][k];
		dodaj[v][k]=0;
	}
}
void updd(int v, int l, int r, int a, int b, ll x, int k) {
	if(r<a || l>b) return;
	if(a<=l && r<=b) {
		if(tr[v][k]==zle) dodaj[v][k]+=x;
		else tr[v][k].st+=x;
		return;
	}
	spl(v, k);
	int mid=(l+r)/2;
	updd(2*v, l, mid, a, b, x, k);
	updd(2*v+1, mid+1, r, a, b, x, k);
}
void upds(int v, ll l, ll r, int a, int b, ll x, ll y, int k) {
	if(r<a || l>b) return;
	if(a<=l && r<=b) {
		dodaj[v][k]=0;
		tr[v][k]={x+y*l, y};
		return;
	}
	spl(v, k);
	int mid=(l+r)/2;
	upds(2*v, l, mid, a, b, x, y, k);
	upds(2*v+1, mid+1, r, a, b, x, y, k);
}
ll pytaj(ll v, int l, int r, int x, int k) {
	if(l==r) return tr[v][k].st;
	spl(v, k);
	int mid=(l+r)/2;
	if(x<=mid) return pytaj(2*v, l, mid, x, k);
	return pytaj(2*v+1, mid+1, r, x, k);
}
pair<ll,ll>jakie(int l, int r) {
	l+=N; r+=N;
	pair<ll,ll>ans=max(pytanie[l], pytanie[r]);
	while(l/2!=r/2) {
		if(l%2==0) ans=max(ans, pytanie[l+1]);
		if(r%2==1) ans=max(ans, pytanie[r-1]);
		l/=2; r/=2;
	}
	return ans;
}
vector<ll>minimum_costs(vector<int>H, vector<int>L, vector<int>R) { 
	int n=H.size();
	while(N<=n) N*=2;
	rep(i, N) ile[N+i]=1;
	for(int i=N-1; i; --i) ile[i]=ile[2*i]+ile[2*i+1];
	rep(i, n) {
		T[i]={H[i], i};
		pytanie[N+i]={H[i], i};
	}
	for(int i=N-1; i; --i) pytanie[i]=max(pytanie[2*i], pytanie[2*i+1]);
	rep(i, L.size()) V[jakie(L[i], R[i]).nd].pb({{L[i], R[i]}, i});
	vector<ll>wyniki(L.size());
	sort(T, T+n);
	S.insert({-LIM, -LIM});
	S.insert({LIM, LIM});
	rep(i, n) {
		for(auto j : V[T[i].nd]) {
			wyniki[j.nd]=pytaj(1, 0, N-1, j.st.nd, 0)+(T[i].nd-j.st.st+1)*T[i].st;
			wyniki[j.nd]=min(wyniki[j.nd], pytaj(1, 0, N-1, n-j.st.st, 1)+(j.st.nd-T[i].nd+1)*T[i].st);
		}
		auto it=S.lower_bound({T[i].nd, T[i].nd});
		auto prawo=*it; --it;
		auto lewo=*it;
		pair<ll,ll>lewod={T[i].nd, T[i].nd}, prawod={T[i].nd, T[i].nd};
		if(lewo.nd==T[i].nd-1) {
			S.erase(lewo);
			lewod.st=lewo.st;
		}
		if(prawo.st==T[i].nd+1) {
			S.erase(prawo);
			prawod.nd=prawo.nd;
		}
		updd(1, 0, N-1, prawod.st, prawod.nd, T[i].st*(lewod.nd-lewod.st+1), 0);
		// znajduje ostatni element na ktorym dp[T[i].nd-1]+(po-T[i].nd+1)*T[i].st<pytaj(po)
		ll dplewo=0, po=prawod.st, ko=prawod.nd;
		if(lewod.st!=T[i].nd) dplewo=pytaj(1, 0, N-1, T[i].nd-1, 0);
		while(po<ko) {
			ll sr=(po+ko+1)/2;
			if(dplewo+(sr-T[i].nd+1)*T[i].st<=pytaj(1, 0, N-1, sr, 0)) po=sr; else ko=sr-1;
		}
		upds(1, 0, N-1, T[i].nd, po, dplewo+(1-T[i].nd)*T[i].st, T[i].st, 0);
		updd(1, 0, N-1, n-lewod.nd, n-lewod.st, T[i].st*(prawod.nd-prawod.st+1), 1);
		// znajduje pierwszy element na ktorym dpprawo+(T[i].nd-sr+1)*T[i].st<pytaj(sr)
		ll dpprawo=0; po=lewod.st; ko=lewod.nd;
		if(prawod.st!=prawod.nd) dpprawo=pytaj(1, 0, N-1, n-T[i].nd-1, 1);
		while(po<ko) {
			ll sr=(po+ko)/2;
			if(dpprawo+(T[i].nd-sr+1)*T[i].st<=pytaj(1, 0, N-1, n-sr, 1)) ko=sr; else po=sr+1;
		}
		upds(1, 0, N-1, n-T[i].nd, n-po, dpprawo+(T[i].nd+1-n)*T[i].st, T[i].st, 1);
		S.insert({lewod.st, prawod.nd});
	}
	return wyniki;
}

Compilation message (stderr)

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:6:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
meetings.cpp:83:2: note: in expansion of macro 'rep'
   83 |  rep(i, L.size()) V[jakie(L[i], R[i]).nd].pb({{L[i], R[i]}, i});
      |  ^~~

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