Submission #1026249

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026249		Lalic	Meetings (IOI18_meetings)	C++17	19 / 100	232 ms	202836 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mp make_pair

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> cd;

const int MAXN = 1e5+10;
const ll LINF = 0x3f3f3f3f3f3f3f3f;

struct Node{
	int sum, pref, suff, ans;
	
	Node(int a=0, int b=0, int c=0, int d=0): sum(a), pref(b), suff(c), ans(d) {}
	
	Node operator+ (Node a) const{
		Node res;
		res.sum=this->sum+a.sum;
		res.pref=max(this->pref, this->sum+a.pref);
		res.suff=max(this->suff+a.sum, a.suff);
		res.ans=max({this->ans, a.ans, this->suff+a.pref});
		return res;
	}
};

Node tree[4*MAXN];

void upd(int node, int l, int r, int p, int val){
	if(r<p || l>p) return;
	if(l==r){
		tree[node]=Node(val, val, val, val);
		return;
	}
	
	int mid=(l+r)>>1;
	upd(node*2, l, mid, p, val); upd(node*2+1, mid+1, r, p, val);
	
	tree[node]=tree[node*2]+tree[node*2+1];
}

Node query(int node, int l, int r, int p, int q){
	if(r<p || l>q) return Node(-1e6, -1e6, -1e6, -1e6);
	if(l>=p && r<=q) return tree[node];
	
	int mid=(l+r)>>1;
	
	return query(node*2, l, mid, p, q)+query(node*2+1, mid+1, r, p, q);
}

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
	int q=(int)L.size(), n=(int)H.size();
	
	if(n<=5000){
		vector<ll> ans(q);
		vector<vector<ll>> res(n, vector<ll>(n));
		
		for(int i=0;i<n;i++){
			res[i][i]=H[i];
			int curr=H[i];
			for(int j=i+1;j<n;j++){
				curr=max(curr, H[j]);
				res[i][j]=res[i][j-1]+curr;
			}
			
			curr=H[i];
			for(int j=i-1;j>=0;j--){
				curr=max(curr, H[j]);
				res[i][j]=res[i][j+1]+curr;
			}
		}
		
		for(int i=0;i<q;i++){
			ll best=LINF;
			for(int j=L[i];j<=R[i];j++) best=min(best, res[j][L[i]]+res[j][R[i]]-H[j]);
			ans[i]=best;
		}
		
		return ans;
	}
	
	for(int i=0;i<n;i++){
		if(H[i]==1) upd(1, 0, n-1, i, 1);
		else upd(1, 0, n-1, i, -1e6);
	}
	
	vector<ll> ans(q);
	for(int i=0;i<q;i++){
		Node interv=query(1, 0, n-1, L[i], R[i]);
		
		//~ cout << interv.ans << "\n";
		int res=2*(R[i]-L[i]+1);
		if(interv.ans>=0) res-=interv.ans;
		
		ans[i]=res;
	}
	
	return ans;
}

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