Submission #244117

#	Time	Username	Problem	Language	Result	Execution time	Memory
244117		crossing0ver	Meetings (IOI18_meetings)	C++17	19 / 100	544 ms	196856 KiB

meetings

#include<bits/stdc++.h>
#define ll long long 
#define pb push_back
#define vi vector<int>
#define fi first
#define se second
#define local

#ifndef local
#include "meetings.h"
#endif
using namespace std;
const int N = 1e5+5;
int Q,n;
ll DD[5005][5005];
pair<int,pair<int,int> > t[4*N];
int F[N][2];

void build(int v,int tl,int tr,vi& H) {
	if (tl == tr) {
		int s = H[tl] == 1;
	t[v] = {s,{s,s} };
	return;
	}
	int tm = (tl + tr)/2;
	build(v*2,tl,tm,H);
	build(v*2+1,tm+1,tr,H);
	t[v].fi = max({t[v*2].fi,t[v*2+1].fi,t[v*2].se.se + t[v*2+1].se.fi});
	t[v].se.fi = t[v*2].se.fi;
	if (t[v*2].se.fi == tm - tl + 1) t[v].se.fi += t[v*2+1].se.fi;
	t[v].se.se = t[v*2+1].se.se;
	if (t[v*2+1].se.se == tr - tl) t[v].se.se += t[v*2].se.se;
}
pair<int,pair<int,int> >  get(int v,int tl,int tr,int l,int r) {
	if (r < tl || l > tr) return{0,{0,0}};
	if (l <= tl && r >= tr) {
		return {t[v].fi,{t[v].se.fi,t[v].se.se}};
	}
	int tm = (tl + tr)/2;
	auto x1 = get(v*2,tl,tm,l,r);
	auto x2 = get(v*2+1,tm+1,tr,l,r);
	pair<int,pair<int,int> > x;
	x.fi = max({x1.fi,x2.fi,x1.se.se + x2.se.fi});
	x.se.fi = x1.se.fi;
	if (x1.se.fi == tm - tl + 1) x.se.fi += x2.se.fi;
	x.se.se = x2.se.se;
	if (x2.se.se == tr - tl) x.se.se += x1.se.se;
	return x;
}


vector<ll> small(vi H,vi L,vi R) {
	vector<ll> T(Q);
	vector<int> e = H,WW(n);
	sort(e.begin(),e.end());
	map<int,int> mp;
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		if (i == 0 || e[i-1] != e[i]) {
			mp[e[i]] = cnt;
			WW[cnt] = e[i];
			cnt++;
		}
	}
	for (int i = 0; i < n; i++) {
		int val = 0;
		ll sum = 0;
		for (int j = i; j >= 0; j--) {
			val = max(val,H[j]);
			sum += val;
			DD[i][j] = sum; 
		}
		sum = 0; val = 0;
		for (int j = i; j < n; j++) {
			val = max(val,H[j]);
			sum += val;
			DD[i][j] = sum;
		}
	}
	for (int i = 0; i < Q; i++) {
		int l = L[i], r = R[i];
		ll ans = LLONG_MAX;
		for (int x = l ; x <= r; x++) {
			ll sum = DD[x][r] + DD[x][l] - H[x];
			ans = min(ans,sum);
		}
		T[i] = ans;
	}
	return T;
}
vector<ll> case2(vi H,vi L,vi R) {
	stack<int> s;
	vector<ll> T(Q);
	build(1,0,n-1,H);
	for (int i = 0; i < n; i++) {
		while (!s.empty() && H[s.top()] <= H[i]) s.pop();
		F[i][0] = (s.size() ? s.top() : i);
		s.push(i);
	}
	while(!s.empty()) s.pop();
	for (int i = n-1; i >= 0; i--) {
		while (!s.empty() && H[s.top()] <= H[i]) s.pop();
		F[i][1] = (s.size() ? s.top() : i);
		s.push(i);
	}
	for (int i = 0; i < Q;i ++) {
		int l = L[i], r = R[i];
		T[i] = 2*(r - l + 1) - get(1,0,n-1,l,r).fi;
	}
	return T;
	
}

vector<ll> minimum_costs(vi H, vi L,vi R) {
  n = H.size(); Q = L.size();
  if (n <= 5000 && Q <= 5000) return small(H,L,R);
  return case2(H,L,R);
  std::vector<long long> C(Q);
  for (int j = 0; j < Q; ++j) {
    C[j] = H[L[j]];
  }
}

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