Submission #132592

#	Time	Username	Problem	Language	Result	Execution time	Memory
132592		dvdg6566	Meetings (IOI18_meetings)	C++14	36 / 100	257 ms	198084 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef vector<ll> vi;
typedef vector<pi> vpi;
#define mp make_pair
#define pb emplace_back
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (ll)x.size()
#define lb lower_bound
#define ub upper_bound

ll A[100100];

struct SparseTable{
	ll N,K;
	vector<vpi> ST;
	SparseTable(ll _N){
		N=_N;K=MSB(N);
		ST.resize(K);
		for (ll i=0;i<N;++i)ST[0].pb(mp(i,A[i]));
		for (ll k=1;k<K;++k){
			for (ll i=0;i+(1<<k)<=N;++i){
				if (ST[k-1][i].s > ST[k-1][i+(1<<(k-1))].s){
					ST[k].pb(ST[k-1][i]);
				}
				else ST[k].pb(ST[k-1][i+(1<<(k-1))]);
			}
		}
	}
	inline int MSB(unsigned int x){return 32-__builtin_clz(x);}
	pi query(ll x, ll y){
		ll k = MSB(y-x+1)-1;
		if (ST[k][x].s > ST[k][y-(1<<k)+1].s)return ST[k][x];
		return ST[k][y-(1<<k)+1];
	}
}*S;

ll memo[5010][5010];

ll ask(ll x, ll y){
	if (memo[x][y] != -1)return memo[x][y];
	if (x==y)return memo[x][y] = A[x];
	pi tall = S->query(x,y);
	// cout<<"Tall "<<tall.f<<' '<<tall.s<<'\n';
	// Answer is on one side of tall
	if (tall.f == x){
		return memo[x][y] = A[x] + ask(x+1,y);
	}
	if (tall.f == y){
		return memo[x][y] = A[y] + ask(x,y-1);
	}
	ll l = ask(x,tall.f-1);
	ll r = ask(tall.f+1,y);
	ll ld = tall.f-x+1;
	ll rd = y-tall.f+1;
	return memo[x][y] = min(ld*tall.s+r, rd*tall.s+l);
}

ll N,Q;

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
  N = SZ(H);
  Q = SZ(L);
  std::vector<long long> C(Q);
  for (ll j = 0; j < Q; ++j) {
    C[j] = -1;
  }
  if (Q <= 5000){
  	for (ll i=0;i<N;++i)A[i]=H[i];
  	S = new SparseTable(N);
  	memset(memo,-1,sizeof(memo));
  	for (ll i=0;i<Q;++i){
  		C[i] = ask(L[i],R[i]);
  	}
  }else{
  	vpi V,ones,twos;
  	set<int> ends, starts;
  	for (int i=0;i<N;++i){
  		if (SZ(V) == 0 || H[i] != V.back().f){
  			if (SZ(V)){
  				if (V.back().f == 1)ones.pb(mp(V.back().s, i-1));
  				else twos.pb(mp(V.back().s, i-1));
  			}
  			V.pb(mp(H[i], i));
  		}
  	}
  	if (V.back().f == 1)ones.pb(mp(V.back().s, N-1));
  	else twos.pb(mp(V.back().s, N-1));
  	// cout<<"Ones\n";
  	// for (auto i : ones)cout<<i.f<<' '<<i.s<<'\n';
  	// cout<<"Twos\n";
  	// for (auto i : twos)cout<<i.f<<' '<<i.s<<'\n';
  	for (auto i : ones){
  		for (int x=i.f;x<=i.s;++x)A[x] = i.s-i.f+1;
  	}
    S = new SparseTable(N);
    for (auto i : ones){
    	ends.insert(i.s);
    	starts.insert(i.f);
    }
    for (int i=0;i<Q;++i){
    	ll maxlen = 0;
    	ll l=L[i];
    	ll r=R[i];
    	if(A[l] != 0){
    		ll x = *ends.lb(l);
    		maxlen = max(maxlen, min(x,r)-l+1);
    		l=x+1;
    	}
    	if(A[r] != 0){
    		ll x = *(--starts.ub(r));
    		maxlen = max(maxlen, r-max(l,x)+1);
    		r=x-1;
    	}
    	// cout<<maxlen<<' '<<l<<' '<<r<<'\n';
    	if (l<=r) maxlen = max(maxlen, S->query(l,r).s);
    	C[i] = 2*(R[i]-L[i]+1) - maxlen;
    }
  }
  return C;
}

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