제출 #111958

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
111958		mechfrog88	모임들 (IOI18_meetings)	C++14	19 / 100	699 ms	786436 KiB

meetings

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

int k;
vector<int> s;
vector<int> diff;

void build(int id = 1, int l=0,int r = k){
	if (r - l < 2){
		s[id] = diff[l];
		return;
	}
	int mid = (l+k)/2;
	build(id*2,l,mid);
	build(id*2+1,mid,r);
	s[id] = min(s[id*2],s[id*2+1]);
}

int query(int x,int y,int id = 1,int l =0,int r = k){
	if (y <= l || x >= r) return INT_MAX;
	if (x <= l && r <= y){
		return s[id];
	}
	int mid = (l+r)/2;
	return min(query(x,y,id*2,l,mid),query(x,y,id*2+1,mid,r));
}

vector<ll> minimum_costs(vector<int> h,vector<int> l,vector<int> r) {
  int n = l.size();
  int a = h.size();
  vector<ll> c(n);
  bool sub3 = true;
  for (int z=0;z<a;z++){
  	if (h[z] > 2){
  		sub3 = false;
  		break;
  	}
  }
  if (sub3){
  	  vector<int> high;
  	  for (int z=0;z<a;z++){
  	  	if (h[z] == 2) {
  	  		high.push_back(z);
  	  		if (high.size() >= 2){
  	  			diff.push_back(*high.rbegin()-(*(high.rbegin()+1))-1);
  	  		}
  	  	}
  	  }
  	  k = diff.size();
  	  if (k != 0){
  	  	s.resize(k*2,INT_MAX);
  	  	build();
  	  }
  	  for (int z=0;z<n;z++){
  	  	int left = l[z];
  	  	int right = r[z];
  	  	if (left == right){
  	  		c[z] = h[z]; continue;
  	  	}
  	  	if (high.size() == 0){
  	  		c[z] = (right-left+1);
  	  		continue;
  	  	}
  	  	auto it = lower_bound(high.begin(),high.end(),left);
  	  	auto ita = lower_bound(high.begin(),high.end(),right);
  	  	c[z] = LLONG_MAX;
  	  	if (it == ita){
  	  		c[z] = (right-left+1);
  	  		if (*it == left) {
  	  			c[z]--;
  	  			c[z] += 2;
  	  		}
  	  		if (*ita == right) {
  	  			c[z]--;
  	  			c[z] += 2;
  	  		}
  	  		continue;
  	  	}
  	  	ll x = *it;
  	  	ll y;
  	  	if (*ita == right){
  	  		y = *(ita);
  	  	} else {
  	  		y = *(ita-1);
  	  	}
  	  	c[z] = min((right-y)+2*(y-left+1),(x-left)+2*(right-x+1));
  	  	ll r;
  	  	if (*ita != right){
  	  		r = query(it-high.begin(),ita-high.begin()-1);
  	  	} else {
  	  		r = query(it-high.begin(),ita-high.begin());
  	  	}
  	  	if (r != LLONG_MAX)
  	  	c[z] = min(c[z],r+2*(right-left+1-r));	
  	  }
  	  return c;
  }
  else{
  	vector <vector<ll>> d(a,vector<ll>(a,0));
  	for (int z=0;z<a;z++){
  		ll maxi = h[z];
  		d[z][z] = h[z];
  		for (int x=z+1;x<a;x++){
  			maxi = max(maxi,ll(h[x]));
  			d[z][x] = d[z][x-1] + maxi;
  		}
  		maxi = h[z];
  		for (int x=z-1;x>-1;x--){
  			maxi = max(maxi,ll(h[x]));
  			d[z][x] = d[z][x+1] + maxi;
  		}
  	}
  	for (int z=0;z<n;z++){
  		ll left = l[z];
  		ll right = r[z];
  		c[z] = LLONG_MAX;
  		for (int x=left;x<=right;x++){
  			c[z] = min(c[z],d[x][right]+d[x][left]-ll(h[x]));
  		}
  	}
  	return c;
  } 
  
}

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