Submission #596307

#	Time	Username	Problem	Language	Result	Execution time	Memory
596307		FatihSolak	Meetings (IOI18_meetings)	C++17	41 / 100	3972 ms	16708 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#define N 100005
using namespace std;
struct SegTree{
	vector<long long> t,lazy;
	int n;
	SegTree(int size){
		n = size;
		t.assign(4*n,0);
		lazy.assign(4*n,0);
	}
	void push(int v){
		t[v*2] += lazy[v];
		t[v*2+1] += lazy[v];
		lazy[v*2] += lazy[v];
		lazy[v*2+1] += lazy[v];
		lazy[v] = 0;
	}
	void upd(int v,int tl,int tr,int l,int r,long long val){
		if(tr < l || r < tl){
			return;
		}
		if(l <= tl && tr <= r){
			t[v] += val;
			lazy[v] += val;
			return;
		}
		push(v);
		int tm = (tl + tr)/2;
		upd(v*2,tl,tm,l,r,val);
		upd(v*2+1,tm+1,tr,l,r,val);
		t[v] = min(t[v*2],t[v*2+1]);
	}
	long long get(int v,int tl,int tr,int l,int r){
		if(tr < l || r < tl){
			return 1e18;
		}
		if(l <= tl && tr <= r){
			return t[v];
		}
		push(v);
		int tm = (tl + tr)/2;
		return min(get(v*2,tl,tm,l,r),get(v*2+1,tm+1,tr,l,r));
	}
	void upd(int l,int r,long long val){
		upd(1,0,n-1,l,r,val);
	}
	long long get(int l,int r){
		return get(1,0,n-1,l,r);
	}
};
int lval[N][2];
int rval[N][2];
vector<int> pos[N];
vector<long long> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
	int q = l.size();
	int n = h.size();
	SegTree t(n);
	int maxi = 0;
	for(int i = 0;i<n;i++){
		maxi = max(maxi,h[i]);
		t.upd(i,i,-h[i]);
	}
	vector<int> st0,st1;
	for(int i = 0;i<n;i++){
		while(st0.size() && h[st0.back()] <= h[i])
			st0.pop_back();
		while(st1.size() && h[st1.back()] < h[i])
			st1.pop_back();
		lval[i][0] = lval[i][1] = -1;
		if(st0.size()){
			lval[i][0] = st0.back();
		}
		if(st1.size()){
			lval[i][1] = st1.back();
		}
		st0.push_back(i);
		st1.push_back(i);
	}
	st0.clear(),st1.clear();
	for(int i = n-1;i>=0;i--){
		while(st0.size() && h[st0.back()] <= h[i])
			st0.pop_back();
		while(st1.size() && h[st1.back()] < h[i])
			st1.pop_back();
		rval[i][0] = rval[i][1] = n;
		if(st0.size()){
			rval[i][0] = st0.back();
		}
		if(st1.size()){
			rval[i][1] = st1.back();
		}
		st0.push_back(i);
		st1.push_back(i);
	}
	//cout << endl;
	for(int i = 0;i<n;i++){
		//cout << i << " " << rval[i][1] << " " << lval[i][0] << endl;
		t.upd(i,rval[i][1] - 1,(long long)h[i] * (i - lval[i][0]));
		t.upd(lval[i][1] + 1,i,(long long)h[i] * (rval[i][0] - i));
	}

	for(int i = 0;i<n;i++){
		pos[h[i]].push_back(i);
	}
	for(int i = 1;i<=maxi;i++){
		pos[i].push_back(n);
	}
	// for(int i = 0;i<n;i++){
	// 	cout << t.get(i,i) << " ";
	// }
	// cout << endl;
	vector<long long> res(q);
	for(int i = 0;i<q;i++){
		vector<pair<pair<int,int>,long long>> changes;
		for(int j = 1;j<=maxi;j++){
			int lpos,rpos;
			if(pos[j][0] < l[i]){
				lpos = prev(lower_bound(pos[j].begin(),pos[j].end(),l[i])) - pos[j].begin();
				long long val = (long long)(pos[j][lpos] - lval[pos[j][lpos]][0]) * j;
				changes.push_back({ {pos[j][lpos], rval[pos[j][lpos]][1]-1}   ,-val});
			}
			if(pos[j].size() > 1 && pos[j][pos[j].size() - 2] > r[i]){
				rpos = upper_bound(pos[j].begin(),pos[j].end(),r[i]) - pos[j].begin();
				long long val = (long long)(rval[pos[j][rpos]][0] - pos[j][rpos]) * j;
				changes.push_back({ { lval[pos[j][rpos]][1]+1,pos[j][rpos]}   ,-val});
			}
			if(*lower_bound(pos[j].begin(),pos[j].end(),l[i]) > r[i])continue;
			lpos = lower_bound(pos[j].begin(),pos[j].end(),l[i]) - pos[j].begin();
			rpos = prev(upper_bound(pos[j].begin(),pos[j].end(),r[i])) - pos[j].begin();
			if(lval[pos[j][lpos]][0] + 1 < l[i]){
				long long val = (long long)(l[i] - lval[pos[j][lpos]][0] - 1) * j;
				int ll = lpos,rr = rpos;
				while(ll < rr){
					int m = (ll + rr + 1)/2;
					if(lval[pos[j][m]][0] < l[i]){
						ll = m;
					}
					else rr = m-1;
				}
				changes.push_back({ {pos[j][lpos], rval[pos[j][ll]][1]-1}   ,-val});
			}
			if(rval[pos[j][rpos]][0] - 1 > r[i]){
				long long val = (long long)(rval[pos[j][rpos]][0] - r[i] - 1) * j;
				int ll = lpos,rr = rpos;
				while(ll < rr){
					int m = (ll + rr)/2;
					if(rval[pos[j][m]][0] > r[i]){
						rr = m;
					}
					else ll = m+1;
				}
				changes.push_back({ { lval[pos[j][ll]][1]+1,pos[j][rpos]}   ,-val});
			}

		}
		for(auto u:changes){
			t.upd(u.first.first,u.first.second,u.second);
		}
		// for(int i = 0;i<n;i++){
		// 	cout << t.get(i,i) << " ";
		// }
		// cout << endl;
		res[i] = t.get(l[i],r[i]);
		for(auto u:changes){
			t.upd(u.first.first,u.first.second,-u.second);
		}
	}
	return res;
}

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