oj.uz

Submission #818071

# Submission time Handle Problem Language Result Execution time Memory
818071 2023-08-10T01:33:53 Z sofapuden Meetings (IOI18_meetings) C++14
17 / 100
 2256 ms 60008 KB 
#include "meetings.h"
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

vector<vector<int>> bitl, bitr, sparse;
vector<vector<ll>> vall, valr;
vector<int> h;

ll c(int l, int r, int x){
	if(x > r || x < l)return (1ll<<60);
	int cul = x;
	ll ans = -h[x];
	for(int i = 18; ~i; --i){
		if(bitl[i][cul] >= l){
			ans+=vall[i][cul];
			cul = bitl[i][cul];
		}
	}
	ans += (cul - l + 1) * h[cul];
	int cur = x;
	for(int i = 18; ~i; --i){
		if(bitr[i][cur] <= r){
			ans+=valr[i][cur];
			cur = bitr[i][cur];
		}
	}
	ans += (r - cur + 1) * h[cur];
	return ans;
}

int merge(int l, int r){
	int cnt = 31 - __builtin_clz(r - l);
	int k = (1<<cnt) - 1;
	ll val = (1ll << 60);
	int id = 0;
	ll z = c(l,r,sparse[cnt][l]);
	if(z < val)id = sparse[cnt][l], val = z;
	z = c(l,r,sparse[cnt][r - k]);
	if(z < val)id = sparse[cnt][r - k], val = z;
	z = c(l,r,l+k);
	if(z < val)id = l + k, val = z;
	z = c(l,r,r - k);
	if(z < val)id = r - k, val = z;
	z = c(l,r,l+k+1);
	if(z < val)id = l + k+1, val = z;
	z = c(l,r,r - k-1);
	if(z < val)id = r - k-1, val = z;
	return id;
}

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
	h = H;
	int n = H.size();
	int q = L.size();
	vector<int> pl, pr;
	vector<int> cu;
	for(int i = 0; i < n; ++i){
		while(cu.size() && H[cu.back()] <= H[i])cu.pop_back();
		pl.push_back(cu.size() ? cu.back() : i);
		cu.push_back(i);
	}
	cu.clear();
	for(int i = n-1; ~i; --i){
		while(cu.size() && H[cu.back()] <= H[i])cu.pop_back();
		pr.push_back(cu.size() ? cu.back() : i);
		cu.push_back(i);
	}
	reverse(pr.begin(),pr.end());
	bitl.resize(19, vector<int>(n));
	bitr.resize(19, vector<int>(n));
	sparse.resize(19, vector<int>(n));
	vall.resize(19, vector<ll>(n));
	valr.resize(19, vector<ll>(n));
	for(int i = 0; i < n; ++i){
		bitl[0][i] = pl[i];
		vall[0][i] = 1ll * (i - pl[i]) * H[i];
	}
	for(int i = 0; i < n; ++i){
		bitr[0][i] = pr[i];
		valr[0][i] = 1ll * (pr[i] - i) * H[i];
	}
	for(int i = 1; i < 19; ++i){
		for(int j = 0; j < n; ++j){
			bitl[i][j] = bitl[i-1][bitl[i-1][j]];
			vall[i][j] = vall[i-1][bitl[i-1][j]] + vall[i-1][j];
			bitr[i][j] = bitr[i-1][bitr[i-1][j]];
			valr[i][j] = valr[i-1][bitr[i-1][j]] + valr[i-1][j];
		}
	}

	iota(sparse[0].begin(),sparse[0].end(),0);
	for(int i = 1; i < 19; ++i){
		for(int j = 0; j < n; ++j){
			if(j + (1<<i) - 1 >= n)break;
			sparse[i][j] = merge(j, j + (1 << i) - 1);
		}
	}
	vector<ll> ans;
	for(int i = 0; i < q; ++i){
		if(L[i] == R[i])ans.push_back(H[L[i]]);
		else ans.push_back(c(L[i],R[i],merge(L[i],R[i])));
	}
	return ans;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 11 ms 1876 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 11 ms 1876 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 143 ms 6016 KB Output is correct
3 Correct 2256 ms 59900 KB Output is correct
4 Correct 1167 ms 60008 KB Output is correct
5 Correct 1501 ms 59900 KB Output is correct
6 Correct 1684 ms 59856 KB Output is correct
7 Correct 1309 ms 59908 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 143 ms 6016 KB Output is correct
3 Correct 2256 ms 59900 KB Output is correct
4 Correct 1167 ms 60008 KB Output is correct
5 Correct 1501 ms 59900 KB Output is correct
6 Correct 1684 ms 59856 KB Output is correct
7 Correct 1309 ms 59908 KB Output is correct
8 Incorrect 1811 ms 59776 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 11 ms 1876 KB Output isn't correct
3 Halted 0 ms 0 KB -