Submission #858939

#	Time	Username	Problem	Language	Result	Execution time	Memory
858939		waldi	Meetings (IOI18_meetings)	C++17	19 / 100	5586 ms	490628 KiB

meetings

#ifndef LOCAL
#include "meetings.h"
#endif
#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define inf 1000000000000000000ll
using namespace std;
typedef long long ll;

vector<ll> minimum_costs(vector<int> h, vector<int> l, vector<int> p){
	int n = h.size();
	int q = l.size();
	
	if(n <= 5000 && q <= 5000){
		vector maks(n, vector(n, 0));
		REP(i, n){
			maks[i][i] = h[i];
			FOR(j, i+1, n-1) maks[i][j] = max(maks[i][j-1], h[j]);
		}
		vector doprawej(n, vector(n, 0ll));
		vector dolewej(n, vector(n, 0ll));
		REP(i, n){
			doprawej[i][i] = dolewej[i][i] = h[i];
			FOR(j, i+1, n-1) dolewej[i][j] = dolewej[i][j-1]+maks[i][j];
			for(int j = i; ~--j;) doprawej[j][i] = doprawej[j+1][i]+maks[j][i];
		}
		vector<ll> ret(q);
		REP(nr, q){
			int a = l[nr], b = p[nr];
			ret[nr] = inf;
			FOR(i, a, b) ret[nr] = min(ret[nr], doprawej[a][i]+dolewej[i][b]-h[i]);
		}
		return ret;
	}
	
	vector<int> lewo(n, 0), prawo(n, 0);
	REP(i, n) if(h[i] == 1) lewo[i] = 1 + (i ? lewo[i-1] : 0);
	for(int i = n; ~--i;) if(h[i] == 1) prawo[i] = 1 + (i+1<n ? prawo[i+1] : 0);
	
	struct przedzialowiec{
		int N;
		vector<int> drz;
		przedzialowiec(int n){
			for(N = 1; N < n;) N <<= 1;
			drz.resize(N<<1, 0);
		}
		void ustaw(int poz, int wart){
			for(poz += N, drz[poz] = wart; poz >>= 1;) drz[poz] = max(drz[poz<<1], drz[poz<<1|1]);
		}
		int maks(int p, int k){
			int ret = 0;
			for(p+=N, k+=N+1; p<k;){
				if(p&1) ret = max(ret, drz[p++]);
				if(k&1) ret = max(ret, drz[--k]);
			}
			return ret;
		}
	} prz(n);
	REP(i, n) prz.ustaw(i, prawo[i]);
	
	vector<ll> ret(q);
	REP(nr, q){
		int a = l[nr], b = p[nr];
		int t = lewo[b];
		ret[nr] = max(t, prz.maks(a, b-t));
	}
	return ret;
}
#ifdef LOCAL
int main(){
	int n, q;
	scanf("%d%d", &n, &q);
	vector<int> h(n);
	REP(i, n) scanf("%d", &h[i]);
	vector<int> l(q), p(q);
	REP(i, q) scanf("%d%d", &l[i], &p[i]);
	vector<ll> ret = minimum_costs(h, l, p);
	for(ll x : ret) printf("%lld\n", x);
	return 0;
}
#endif

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