Submission #1148171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148171		Kaztaev_Alisher	Meetings (IOI18_meetings)	C++20	0 / 100	21 ms	2376 KiB

meetings

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

#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second
// #define int ll 

using namespace std;
using ll = long long;

const ll N = 5555 , M = 2e5+5 , inf = 2e9 + 7;
const ll INF = 1e18 ,   mod = 1e9+7;

ll pr[N][N] , sf[N][N] , a[N];
vector<ll> slow(vector<int> H, vector<int> L, vector<int> R){
	int Q = L.size();
	int n = H.size();
	vector<long long> C(Q);
	for(int i = 1; i <= n; i++){
		a[i] = H[i-1];
	}
	for(int l = 1; l <= n; l++){
		ll mx = a[l];
		for(int r = l; r <= n; r++){
			mx = max(mx , a[r]);
			pr[l][r] = pr[l][r-1] + mx;
		}	
	}
	for(int r = n; r >= 1; r--){
		ll mx = a[r];
		for(int l = r; l >= 1; l--){
			mx = max(mx , a[l]);
			sf[r][l] = sf[r][l+1] + mx;
		}	
	}
	for(int i = 0; i < Q; i++){
		L[i]++;
		R[i]++;
		C[i] = INF;
		for(int j = L[i]; j <= R[i]; j++){
			C[i] = min(C[i] , pr[j][R[i]]+sf[j][L[i]]-a[j]);
		}
	}
	return C;
}

struct node{
	int l = 0 , r = 0 , sum = 0 , mx = 0;
} t[M*4];

node merge(node a , node b){
	node c;
	c.mx = max({a.mx , b.mx , a.r+b.l});
	c.sum = a.sum + b.sum;
	c.l = max({a.l , b.l+a.sum});
	c.r = max({b.r , a.r+b.sum});
	return c;
}
void build(int v, int tl , int tr){
	if(tl == tr){
		if(a[tl] == 1){
			t[v].l = t[v].r = t[v].sum = t[v].mx = 1;
		} else {
			t[v].l = t[v].r = t[v].mx = 0;
			t[v].sum = -inf;
		}
		return;
	}
	int tm = (tl+tr) >> 1;
	build(v*2,tl,tm);
	build(v*2+1,tm+1,tr);
	t[v] = merge(t[v*2],t[v*2+1]);
}
node get(int v, int tl , int tr , int l , int r){
	if(l <= tl && tr <= r){
		return t[v];
	} 
	if(tl > r || tr < l) return {0,0,-inf,0};
	int tm = (tl+tr) >> 1;
	return merge(get(v*2,tl,tm,l,r) , get(v*2+1,tm+1,tr,l,r));
}
vector<ll> go(vector<int> H, vector<int> L, vector<int> R){
	int Q = L.size();
	int n = H.size();
	vector<long long> C(Q);
	for(int i = 1; i <= n; i++){
		a[i] = H[i-1];
	}
	build(1,1,n);
	for(int i = 0; i < Q; i++){
		L[i]++;
		R[i]++;
		int len = (R[i]-L[i]+1);
		C[i] = len + len-get(1,1,n,L[i],R[i]).mx;
	}
	return C;
}
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
	// if(H.size() <= 5000 && L.size() <= 5000) return slow(H, L, R);
	return go(H,L,R);
}

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