oj.uz

Submission #111963

# Submission time Handle Problem Language Result Execution time Memory
111963 2019-05-17T01:24:30 Z mechfrog88 Meetings (IOI18_meetings) C++14
19 / 100
 704 ms 196444 KB 
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
ll k;
vector<ll> s;
vector<ll> diff;
 
void build(ll id = 1, ll l=0,ll r = k){
	if (r - l < 2){
		s[id] = diff[l];
		return;
	}
	ll mid = (l+r)/2;
	build(id*2,l,mid);
	build(id*2+1,mid,r);
	s[id] = max(s[id*2],s[id*2+1]);
}
 
ll query(ll x,ll y,ll id = 1,ll l =0,ll r = k){
	if (y <= l || x >= r) return 0;
	if (x <= l && r <= y){
		return s[id];
	}
	ll mid = (l+r)/2;
	return max(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();
  ll 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<ll> high;
  	  for (int z=0;z<a;z++){
  	  	if (h[z] == 2) {
  	  		high.push_back(z);
  	  		if (high.size() >= 2){
  	  			ll temp = *high.rbegin()-(*(high.rbegin()+1))-1;
  	  			diff.push_back(temp);
  	  		}
  	  	}
  	  }
  	  k = diff.size();
  	  if (k != 0){
  	  	s.resize(k*4,0);
  	  	build();
  	  }
  	  for (int z=0;z<n;z++){
  	  	ll left = l[z];
  	  	ll 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());
  	  	}
  	  	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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 83 ms 70940 KB Output is correct
3 Correct 84 ms 70904 KB Output is correct
4 Correct 84 ms 70848 KB Output is correct
5 Correct 84 ms 70880 KB Output is correct
6 Correct 83 ms 70968 KB Output is correct
7 Correct 82 ms 70972 KB Output is correct
8 Correct 84 ms 70912 KB Output is correct
9 Correct 83 ms 70876 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 83 ms 70940 KB Output is correct
3 Correct 84 ms 70904 KB Output is correct
4 Correct 84 ms 70848 KB Output is correct
5 Correct 84 ms 70880 KB Output is correct
6 Correct 83 ms 70968 KB Output is correct
7 Correct 82 ms 70972 KB Output is correct
8 Correct 84 ms 70912 KB Output is correct
9 Correct 83 ms 70876 KB Output is correct
10 Correct 527 ms 196368 KB Output is correct
11 Correct 686 ms 196408 KB Output is correct
12 Correct 528 ms 196384 KB Output is correct
13 Correct 704 ms 196372 KB Output is correct
14 Correct 528 ms 196444 KB Output is correct
15 Correct 538 ms 196384 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 46 ms 1796 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 46 ms 1796 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 83 ms 70940 KB Output is correct
3 Correct 84 ms 70904 KB Output is correct
4 Correct 84 ms 70848 KB Output is correct
5 Correct 84 ms 70880 KB Output is correct
6 Correct 83 ms 70968 KB Output is correct
7 Correct 82 ms 70972 KB Output is correct
8 Correct 84 ms 70912 KB Output is correct
9 Correct 83 ms 70876 KB Output is correct
10 Correct 527 ms 196368 KB Output is correct
11 Correct 686 ms 196408 KB Output is correct
12 Correct 528 ms 196384 KB Output is correct
13 Correct 704 ms 196372 KB Output is correct
14 Correct 528 ms 196444 KB Output is correct
15 Correct 538 ms 196384 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Incorrect 46 ms 1796 KB Output isn't correct
18 Halted 0 ms 0 KB -