oj.uz

Submission #112030

# Submission time Handle Problem Language Result Execution time Memory
112030 2019-05-17T05:54:26 Z mechfrog88 Meetings (IOI18_meetings) C++14
36 / 100
 735 ms 786432 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[left]; 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 (*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)+ll(2)*(y-left+1),(x-left)+ll(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+ll(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 376 KB Output is correct
2 Correct 85 ms 70936 KB Output is correct
3 Correct 84 ms 70904 KB Output is correct
4 Correct 83 ms 70936 KB Output is correct
5 Correct 83 ms 70876 KB Output is correct
6 Correct 82 ms 70876 KB Output is correct
7 Correct 83 ms 70872 KB Output is correct
8 Correct 84 ms 70876 KB Output is correct
9 Correct 85 ms 70904 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 85 ms 70936 KB Output is correct
3 Correct 84 ms 70904 KB Output is correct
4 Correct 83 ms 70936 KB Output is correct
5 Correct 83 ms 70876 KB Output is correct
6 Correct 82 ms 70876 KB Output is correct
7 Correct 83 ms 70872 KB Output is correct
8 Correct 84 ms 70876 KB Output is correct
9 Correct 85 ms 70904 KB Output is correct
10 Correct 511 ms 196440 KB Output is correct
11 Correct 735 ms 196444 KB Output is correct
12 Correct 524 ms 196384 KB Output is correct
13 Correct 735 ms 196344 KB Output is correct
14 Correct 519 ms 196356 KB Output is correct
15 Correct 521 ms 196448 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 45 ms 1872 KB Output is correct
3 Correct 131 ms 7124 KB Output is correct
4 Correct 83 ms 4612 KB Output is correct
5 Correct 63 ms 7120 KB Output is correct
6 Correct 110 ms 7388 KB Output is correct
7 Correct 107 ms 7140 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 45 ms 1872 KB Output is correct
3 Correct 131 ms 7124 KB Output is correct
4 Correct 83 ms 4612 KB Output is correct
5 Correct 63 ms 7120 KB Output is correct
6 Correct 110 ms 7388 KB Output is correct
7 Correct 107 ms 7140 KB Output is correct
8 Runtime error 662 ms 786432 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 85 ms 70936 KB Output is correct
3 Correct 84 ms 70904 KB Output is correct
4 Correct 83 ms 70936 KB Output is correct
5 Correct 83 ms 70876 KB Output is correct
6 Correct 82 ms 70876 KB Output is correct
7 Correct 83 ms 70872 KB Output is correct
8 Correct 84 ms 70876 KB Output is correct
9 Correct 85 ms 70904 KB Output is correct
10 Correct 511 ms 196440 KB Output is correct
11 Correct 735 ms 196444 KB Output is correct
12 Correct 524 ms 196384 KB Output is correct
13 Correct 735 ms 196344 KB Output is correct
14 Correct 519 ms 196356 KB Output is correct
15 Correct 521 ms 196448 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 45 ms 1872 KB Output is correct
18 Correct 131 ms 7124 KB Output is correct
19 Correct 83 ms 4612 KB Output is correct
20 Correct 63 ms 7120 KB Output is correct
21 Correct 110 ms 7388 KB Output is correct
22 Correct 107 ms 7140 KB Output is correct
23 Runtime error 662 ms 786432 KB Execution killed with signal 9 (could be triggered by violating memory limits)
24 Halted 0 ms 0 KB -