Submission #762225

#	Time	Username	Problem	Language	Result	Execution time	Memory
762225		minhcool	Highway Tolls (IOI18_highway)	C++17	Compilation error	0 ms	0 KiB

highway

#define local
#ifndef local
#include "meetings.h"
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<ll, ll> ii;
typedef pair<ii, ll> iii;
typedef pair<ii, ii> iiii;

const ll N = 3e5 + 5;

const ll oo = 1e18 + 7, mod = 1e9 + 7;

mt19937 rng(1);

ll rnd(ll l, ll r){
	ll temp = rng() % (r - l + 1);
	return abs(temp) + l;
}

ll n, q;

ll arr[N], sum[N];

int which[N];

int maxi[N][20];

ii streaks[N];

int gett(ii a, ii b){
//	cout << a.fi << " " << a.se << " " << b.fi << " " << b.se << "\n";
	return max(0LL, (min(a.se, b.se) - max(a.fi, b.fi) + 1));	
}

int get(int l, int r){
	if(l > r) return -1;
	int k = log2(r - l + 1);
	return max(maxi[l][k], maxi[r - (1LL << k) + 1][k]);
}

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
	n = H.size(), q = L.size();
	for(ll i = 0; i < n; i++) arr[i] = H[i];
	if(n <= 5000 && q <= 5000){
		vector<ll> v;
		for(ll i = 0; i < q; i++){
			ll le = L[i], ri = R[i];
			for(ll j = le; j <= ri; j++) sum[j] = 0;
			stack<ii> q;
			ll total = 0;
			for(ll j = le; j <= ri; j++){
				ll tol = 0;
				while(!q.empty() && q.top().fi <= arr[j]){
					tol += q.top().se;
					total += q.top().se * (arr[j] - q.top().fi);
					q.pop();
				}
				tol++;
				total += arr[j];
				sum[j] += total;
				q.push({arr[j], tol});
			}
			while(!q.empty()) q.pop();
			total = 0;
			for(ll j = ri; j >= le; j--){
				ll tol = 0;
				while(!q.empty() && q.top().fi <= arr[j]){
					tol += q.top().se;
					total += q.top().se * (arr[j] - q.top().fi);
					q.pop();
				}
				tol++;
				total += arr[j];
				sum[j] += total;
				q.push({arr[j], tol});
			}
			ll mini = oo;
			for(ll j = le; j <= ri; j++) mini = min(mini, sum[j] - arr[j]);
			v.pb(mini);
		}
		return v;
	}
	else{
		streaks[0] = {-1, -1};
		int lst = -1, cnt = 0;
		for(int i = 0; i <= n; i++){
			if(arr[i] == 1){
				if(lst == -1){
					lst = i;
					cnt++;
				}
			}
			else{
				if(lst != -1){
					streaks[cnt] = {lst, i - 1};
				//	cout << cnt << " " << streaks[cnt].fi << " " << streaks[cnt].se << "\n";
					for(int j = lst; j < i; j++) which[j] = cnt;
					maxi[cnt][0] = (i - lst);
					lst = -1;
				}
				which[i] = cnt;
			}
		}
		for(int i = 1; i <= 19; i++){
			for(int j = 1; (j + (1LL << i) - 1) <= cnt; j++) maxi[j][i] = max(maxi[j][i - 1], maxi[j + (1LL << (i - 1))][i - 1]);
		}
		vector<ll> answer;
		for(int i = 0; i < q; i++){
			int le = L[i], ri = R[i];
			int mx_len = 0;
			if(which[le] == which[ri]) mx_len = max(mx_len, gett(streaks[which[le]], make_pair((ll)le, (ll)ri)));
			else{
				mx_len = max(mx_len, gett(streaks[which[le]], make_pair((ll)le, (ll)ri)));
				mx_len = max(mx_len, gett(streaks[which[ri]], make_pair((ll)le, (ll)ri)));
				mx_len = max(mx_len, get(which[le] + 1, which[ri] - 1));
			}
			answer.pb((ri - le + 1) * 2 - mx_len);
		}
		return answer;
	}
}


#ifdef local
void process(){
	ll n, q;
	cin >> n >> q;
	vector<int> h(n), l(q), r(q);
	for(ll i = 0; i < n; i++) cin >> h[i];
	for(ll i = 0; i < q; i++) cin >> l[i] >> r[i];
	vector<ll> v = minimum_costs(h, l, r);
	for(auto it : v) cout << it << " ";
	cout << "\n";
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	process();
}
#endif

Compilation message (stderr)

/usr/bin/ld: /tmp/ccAgP0gq.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccZ774gp.o:highway.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccAgP0gq.o: in function `main':
grader.cpp:(.text.startup+0x16c): undefined reference to `find_pair(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, int, int)'
collect2: error: ld returned 1 exit status