Submission #738587

#	Time	Username	Problem	Language	Result	Execution time	Memory
738587		huajun	Meetings (IOI18_meetings)	C++14	100 / 100	3692 ms	494408 KiB

meetings

#include "meetings.h"
#include<bitset>
#include<compare>
#include<functional>
#include<tuple>
#include<utility>
#include<cstring>
#include<string>
#include<deque>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<vector>
#include<iterator>
#include<ranges>
#include<algorithm>
#include<random>
#include<fstream>
#include<iostream>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long int ll;
typedef long double ld;
#define mp make_pair
#define pb push_back
#define eb emplace_back
vector<pair<ll,ll> > dq, pa;
ll aj[750005][2], l[750005], r[750005], root, h[750005], ans[750005];
struct node{
	ll s, e, m, lazy, vm, vc;
	node *l, *r;
	node(ll _s, ll _e): s(_s), e(_e), m((_s+_e)/2), lazy(0), vm(0), vc(1e17){
		if(s!=e){
			l = new node(s,m);
			r = new node(m+1, e);
		}
	}
	void propo(){
		if(lazy){
			l->vc += lazy;
			r->vc += lazy;
			l->lazy += lazy;
			r->lazy += lazy;
			lazy = 0;
		}
	}
	void update(ll x,ll y, ll nm, ll nc){
		if(s==x&&y==e){
			if((vm|vc)==0){
				vm = nm;
				vc = nc;
				return;
			}
			if(nm*m+nc < vm*m+vc){
				swap(nm, vm);
				swap(vc, nc);
			}
			if(s!=e){
				propo();
				if(vm > nm)r->update(m+1, e, nm, nc);
				if(vm < nm)l->update(s, m, nm, nc);
			}
			return;
		}
		propo();
		if(y<=m)l->update(x, y, nm, nc);
		else if(x>m)r->update(x, y, nm, nc);
		else{
			l->update(x, m, nm, nc);
			r->update(m+1, y, nm, nc);
		}
	}
	void add(ll x,ll y, ll v){
		if(s==x&&e==y){
			lazy+=v;
			vc+=v;
			return;
		}
		propo();
		if(y<=m)l->add(x, y, v);
		else if(x>m)r->add(x, y, v);
		else{
			l->add(x, m, v);
			r->add(m+1, y, v);
		}
	}
	ll query(ll x){
		ll a = 1e17;
		if(vm | vc){
			a = vm*x+vc;
		}
		if(s==e)return a;
		propo();
		if(x<=m)return min(a, l->query(x));
		else return min(a, r->query(x));
	}
} *rootS, *rootP;
vector<tuple<ll,ll, ll> > v, qn[750005];
vector<pair<ll,ll> > dq2;
void dfs(ll x){
	ll a = 0, b = 0;
	if(~aj[x][0]){
		dfs(aj[x][0]);
		a = rootP->query(x-1);
	}
	if(~aj[x][1]){
		dfs(aj[x][1]);
		b = rootS->query(x+1);
	}
	//cout<<x<<" "<<l[x]<<" "<<r[x]<<" "<<a<<" "<<b<<" val"<<endl;
	for(auto [ql, qr, q]:qn[x]){
	//	cout<<ql<<" "<<qr<<" "<<q<<endl;
	//	cout<<((qr>x)?rootP->query(qr):0)<<" "<<((ql<x)? rootS->query(ql):0)<<" "<<h[x]<<endl;
		ans[q] = min(((qr>x)?rootP->query(qr):0) + (x-ql+1)*h[x],((ql<x)? rootS->query(ql):0)+(qr-x+1)*h[x]);
	}
//	cout<<x<<" "<<l[x]<<" "<<r[x]<<" "<<a<<" "<<b<<" dfs"<<endl;
	rootS->update(x, x, 0, 0);
	rootP->update(x, x, 0, 0);
	rootS->add(l[x], x, (r[x] - x+1)*h[x]);
	if(x>l[x])rootS->add(x, x, (x-l[x])*h[x]);
	rootP->add(x, r[x], (x - l[x]+1)*h[x]);
	if(r[x]>x)rootP->add(x, x, (r[x] - x)*h[x]);
	rootS->update(l[x], x, -h[x], b+(x+1)*h[x]);
	rootP->update(x, r[x], h[x], a+(1-x)*h[x]);
	//cout<<x<<" "<<l[x]<<" "<<r[x]<<" "<<rootP->query(r[x])<<" "<<rootS->query(l[x])<<" dfs"<<endl;
//	for(ll i=0;i<5;i++)cout<<rootP->query(i)<<" ";cout<<"\n";
//	for(ll i=0;i<5;i++)cout<<rootS->query(i)<<" ";cout<<"\n";
}
vector<long long> minimum_costs(vector<int> H, vector<int> L,
                                     vector<int> R) {
  int Q = L.size();
  vector<long long> C(Q);
  int n = H.size();
  ll i,j,k,a,b,c,x,y,z;
  memset(aj, -1, sizeof(aj));
  for(i=0;i<Q;i++){
	v.eb(R[i], L[i], i);
  }
  sort(all(v));
  ll cur = 0;
  for(i=0;i<n;i++){
	  h[i] = H[i];
	pa.eb(2e9, -1);
	auto it = mp((ll)H[i], i);
	while(dq.size()&&dq.back() <= it)dq.pop_back();
	if(dq.size()){
		pa[i] = dq.back();
		l[i] = dq.back().second+1;
	}else l[i] = 0;
	dq.pb(it);
	
	while(dq2.size()&&dq2.back().second<=h[i])dq2.pop_back();
	dq2.pb(mp(i, h[i]));
	while(cur<Q&&get<0>(v[cur])==i){
		a = lower_bound(dq2.begin(), dq2.end(), mp(get<1>(v[cur]), -1ll)) - dq2.begin();
		qn[dq2[a].first].eb(get<1>(v[cur]), get<0>(v[cur]), get<2>(v[cur]));
		cur++;
	}
  }
  dq.clear();
  for(i=n-1;i>=0;i--){
	auto it = mp((ll)H[i], i);
	while(dq.size()&&dq.back() <= it)dq.pop_back();
	if(dq.size()){
		pa[i] = min(dq.back(), pa[i]);
		r[i] = dq.back().second-1;
	}else r[i] = n-1;
	dq.pb(it);
  }
  for(i=0;i<n;i++){
	if(pa[i].second==-1)root = i;
	else{
		aj[pa[i].second][pa[i].second < i] = i;
	}
  }
  rootP = new node(0, n-1);
  rootS = new node(0, n-1);
  dfs(root);
  for(i=0;i<Q;i++)C[i] = ans[i];
  return C;
}

Compilation message (stderr)

meetings.cpp: In function 'void dfs(ll)':
meetings.cpp:117:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  117 |  for(auto [ql, qr, q]:qn[x]){
      |           ^
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:140:8: warning: unused variable 'j' [-Wunused-variable]
  140 |   ll i,j,k,a,b,c,x,y,z;
      |        ^
meetings.cpp:140:10: warning: unused variable 'k' [-Wunused-variable]
  140 |   ll i,j,k,a,b,c,x,y,z;
      |          ^
meetings.cpp:140:14: warning: unused variable 'b' [-Wunused-variable]
  140 |   ll i,j,k,a,b,c,x,y,z;
      |              ^
meetings.cpp:140:16: warning: unused variable 'c' [-Wunused-variable]
  140 |   ll i,j,k,a,b,c,x,y,z;
      |                ^
meetings.cpp:140:18: warning: unused variable 'x' [-Wunused-variable]
  140 |   ll i,j,k,a,b,c,x,y,z;
      |                  ^
meetings.cpp:140:20: warning: unused variable 'y' [-Wunused-variable]
  140 |   ll i,j,k,a,b,c,x,y,z;
      |                    ^
meetings.cpp:140:22: warning: unused variable 'z' [-Wunused-variable]
  140 |   ll i,j,k,a,b,c,x,y,z;
      |                      ^

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