Submission #778841

#	Time	Username	Problem	Language	Result	Execution time	Memory
778841		amunduzbaev	Meetings (IOI18_meetings)	C++17	60 / 100	735 ms	417184 KiB

meetings

#include "meetings.h"

#include "bits/stdc++.h"
using namespace std;

#ifndef EVAL
#include "grader.cpp"
#endif

#define ar array
typedef long long ll;
typedef int32_t ii;
//~ #define int ll

const int N = 1e5 + 5;

struct ST{
	ar<ll, 2> tree[N << 2];
	ar<ll, 2> def;
	
	ST(){
		def = (ar<ll, 2>){(ll)1e18, (ll)1e18};
	}
	
	void set(int i, ll v, int lx, int rx, int x){
		if(lx == rx) { tree[x] = {v, lx}; return; }
		int m = (lx + rx) >> 1;
		if(i <= m) set(i, v, lx, m, x << 1);
		else set(i, v, m + 1, rx, x << 1 | 1);
		tree[x] = min(tree[x << 1], tree[x << 1 | 1]);
	}
	
	void set(int i, ll v){
		set(i, v, 0, N, 1);
	}
	
	ar<ll, 2> get(int l, int r, int lx, int rx, int x){
		if(lx > r || rx < l) return def;
		if(lx >= l && rx <= r) return tree[x];
		int m = (lx + rx) >> 1;
		
		return min(get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1));
	}
	
	ar<ll, 2> get(int l, int r){
		return get(l, r, 0, N, 1);
	}
}tree;

bool check = 1;

vector<ll> minimum_costs(vector<ii> a, vector<ii> l, vector<ii> r) {
	int n = a.size(), q = l.size();
	
	if(n <= 5000 && q <= 5000 && check){
		vector<ll> res(q);
		
		auto get = [&](vector<int> a){
			int n = a.size();
			ll cur = 0;
			vector<int> ss;
			vector<ll> cost(n);
			for(int i=0;i<n;i++){
				while(!ss.empty() && a[ss.back()] <= a[i]){
					int id = ss.back();
					ss.pop_back();
					if(ss.empty()) cur -= a[id] * 1ll * (id + 1);
					else cur -= a[id] * 1ll * (id - ss.back());
				}
				
				if(ss.empty()) cur += a[i] * 1ll * (i + 1);
				else cur += a[i] * 1ll * (i - ss.back());
				ss.push_back(i);
				cost[i] += cur;
			}
			
			ss.clear(); cur = 0;
			for(int i= n - 1;~i;i--){
				while(!ss.empty() && a[ss.back()] <= a[i]){
					int id = ss.back();
					ss.pop_back();
					if(ss.empty()) cur -= a[id] * 1ll * (n - id);
					else cur -= a[id] * 1ll * (ss.back() - id);
				}
				
				if(ss.empty()) cur += a[i] * 1ll * (n - i);
				else cur += a[i] * 1ll * (ss.back() - i);
				ss.push_back(i);
				cost[i] += cur;
			}
			
			ll mn = 1e18;
			for(int i=0;i<n;i++){
				mn = min(mn, cost[i] - a[i]);
			}
			
			return mn;
		};
		
		for(int i=0;i<q;i++){
			vector<int> b;
			for(int j=l[i];j<=r[i];j++){
				b.push_back(a[j]);
			}
			
			res[i] = get(b);
		}
		
		return res;
	}
	
	vector<ll> res(q), cost(n);

	vector<vector<int>> pref(n, vector<int>(20, -1)), suff(n, vector<int>(20, n + 1));
	{
		for(int i=0;i<n;i++){
			if(i) pref[i] = pref[i - 1];
			pref[i][a[i] - 1] = i;
		}
		for(int i=n-1;~i;i--){
			if(i + 1 < n) suff[i] = suff[i + 1];
			suff[i][a[i] - 1] = i;
		}
	}
	
	auto get = [&](int i, int l, int r){
		ll cost = 0;
		for(int j=19;~j;j--){
			if(l <= pref[i][j]){
				cost += (pref[i][j] - l + 1) * 1ll * j;
				l = pref[i][j] + 1;
			}
			if(suff[i][j] <= r){
				cost += (r - suff[i][j] + 1) * 1ll * j;
				r = suff[i][j] - 1;
			}
		}
		
		cost -= (a[i] - 1);
		return cost;
	};
	
	for(int i=0;i<n;i++){
		cost[i] = get(i, 0, n - 1);
		
		tree.set(i, cost[i]);
	}
	
	for(int i=0;i<q;i++){
		int p = -1;
		for(int j=19;~j;j--){
			if(l[i] <= pref[r[i]][j]){
				p = pref[r[i]][j];
				break;
			}
		}
		
		assert(~p);
		int l_ = suff[l[i]][a[p] - 1], r_ = pref[r[i]][a[p] - 1];
		vector<int> pos;
		pos.push_back(tree.get(l_, r_)[1]);
		
		for(int j=19;~j;j--){
			if(suff[l[i]][j] < l_){
				pos.push_back(tree.get(suff[l[i]][j], l_ - 1)[1]);
				l_ = suff[l[i]][j];
			}
			if(r_ < pref[r[i]][j]){
				pos.push_back(tree.get(r_ + 1, pref[r[i]][j])[1]);
				r_ = pref[r[i]][j];
			}
		}
		
		res[i] = 1e18;
		for(auto x : pos){
			res[i] = min(res[i], get(x, l[i], r[i]));
			//~ cout<<x<<" ";
		}
		
		res[i] += (r[i] - l[i] + 1);
		//~ cout<<"\n";
	}
	
	return res;
}

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