Submission #132570

#	Time	Username	Problem	Language	Result	Execution time	Memory
132570		dvdg6566	Meetings (IOI18_meetings)	C++14	0 / 100	84 ms	98888 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef vector<int> 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) (int)x.size()

int A[5010];

struct SparseTable{
	int N,K;
	vector<vpi> ST;
	SparseTable(int _N){
		N=_N;K=MSB(N);
		ST.resize(K);
		for (int i=0;i<N;++i)ST[0].pb(mp(i,A[i]));
		for (int k=1;k<K;++k){
			for (int 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(int x, int y){
		int 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;

int memo[5010][5010];

ll ask(int x, int 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);
	}
	int l = ask(x,tall.f-1);
	int r = ask(tall.f+1,y);
	int ld = tall.f-x+1;
	int rd = y-tall.f+1;
	return memo[x][y] = min(ld*tall.s+r, rd*tall.s+l);
}

int 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 (int j = 0; j < Q; ++j) {
    C[j] = -1;
  }
  if (Q <= 5000){
  	for (int i=0;i<N;++i)A[i]=H[i];
  	S = new SparseTable(N);
  	memset(memo,-1,sizeof(memo));
  	for (int i=0;i<Q;++i){
  		C[i] = ask(L[i],R[i]);
  	}
  }
  return C;
}

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