Submission #425049

#	Time	Username	Problem	Language	Result	Execution time	Memory
425049		Pbezz	Meetings (IOI18_meetings)	C++14	17 / 100	119 ms	8376 KiB

meetings

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

using namespace std;

#define ll long long
#define pb push_back
typedef pair<ll,ll> pii;

const ll MAXN = 100005;
const ll INF = 1e16+7;
ll dp[MAXN],seg[4*MAXN],n;
//seg[node]=min index que maximiza dp[index]

void recalculate(ll node){
//	cout<<node<<" "<<seg[2*node+1]<<" "<<seg[2*node+2]<<endl;
	if(dp[seg[2*node+1]]>=dp[seg[2*node+2]]){
	seg[node]=seg[2*node+1];
	}else if(dp[seg[2*node+1]]<dp[seg[2*node+2]]){
	seg[node]=seg[2*node+2];
	}
}

void build(ll node, ll left, ll right){
if(left==right){
seg[node]=left;
}else{
ll middle = (left+right)/2;

build(2*node+1,left,middle);
build(2*node+2,middle+1,right);
recalculate(node);
}
}

ll querie(ll node, ll left, ll right, ll a, ll b){

if(a<=left&&b>=right){
return seg[node];
}
ll middle = (left+right)/2,k1=n+1,k2=n+1;

if(a<=middle)k1=querie(2*node+1,left,middle,a,b);

if(b>=middle+1)k2=querie(2*node+2,middle+1,right,a,b);

if(a<=middle && dp[k1]>=dp[k2])return k1;
return k2;
}

std::vector<long long> minimum_costs(std::vector<int>H,std::vector<int>L,
                                     std::vector<int> R) {

	int Q = L.size(),i,k,bruh;
	n=(ll)H.size();

	dp[n+1]=0;
	for(i=n;i>=1;i--){

	if(H[i-1]==2){
	dp[i]=0;
	continue;
	}
	dp[i]=dp[i+1]+1;
	}
	build(0,1,n);
//	for(i=1;i<=n;i++){
//cout<<i<<" "<<seg[i]<<endl;
//}
  std::vector<long long> C(Q);

	for(i=0;i<Q;i++){
	L[i]++; R[i]++;

	k = querie(0,1,n,L[i],R[i]);
	if(k+dp[k]-1<=R[i]){
	C[i]=dp[k]+2*(R[i]-L[i]+1-dp[k]);
	continue;
	}

	C[i] = R[i]-k+1;

	if(k>L[i]){

	bruh = querie(0,1,n,L[i],k-1);

	C[i] = max(C[i],dp[bruh]);
	}

	C[i] = C[i]+2*(R[i]-L[i]+1-C[i]);

}

  return C;
}

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