Submission #741709

#	Time	Username	Problem	Language	Result	Execution time	Memory
741709		myrcella	Meetings (IOI18_meetings)	C++17	41 / 100	1293 ms	559204 KiB

meetings

//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

#include "meetings.h"

const int maxn = 1e5+10;
ll hmm[22][22];
struct node{
	vector <pair<pii,ll> > f;
	pair<ll,int> pre[21],suf[21];
	ll mn;
} tree[maxn*4];
int h[maxn];
int n;

node merge(node a,node b) {
	node ret;
	rep(i,1,21) {
		ret.pre[i] = {a.pre[i].fi + b.pre[a.pre[i].se].fi, b.pre[a.pre[i].se].se};
		ret.suf[i] = {b.suf[i].fi + a.suf[b.suf[i].se].fi, a.suf[b.suf[i].se].se};
	}
	//left
	for (auto it:a.f) {
		int l = it.fi.fi;
		int r = b.pre[it.fi.se].se;
		if (hmm[l][r] == -1) ret.f.pb({{l,r},0}),hmm[l][r] = it.se + b.pre[it.fi.se].fi;
		else hmm[l][r] = min(hmm[l][r],it.se + b.pre[it.fi.se].fi);
	}
	//right
	for (auto it:b.f) {
		int r = it.fi.se;
		int l = a.suf[it.fi.fi].se;
		if (hmm[l][r] == -1) ret.f.pb({{l,r},0}),hmm[l][r] = it.se + a.suf[it.fi.fi].fi;
		else hmm[l][r] = min(hmm[l][r],it.se + a.suf[it.fi.fi].fi);
	}
	ret.mn = 1e18;
	rep(i,0,SZ(ret.f)) ret.f[i].se = hmm[ret.f[i].fi.fi][ret.f[i].fi.se], hmm[ret.f[i].fi.fi][ret.f[i].fi.se] = -1,ret.mn = min(ret.mn,ret.f[i].se);
	return ret;
}

void init(int c,int cl,int cr) {
	if (cl==cr) {
		rep(i,1,21) tree[c].pre[i] = tree[c].suf[i] = {max(i,h[cl]),max(i,h[cl])};
		tree[c].f.pb({{h[cl],h[cl]},h[cl]});
		tree[c].mn = h[cl];
		return;
	}
	int mid=cl+cr>>1;
	init(c<<1,cl,mid);
	init(c<<1|1,mid+1,cr);
	tree[c] = merge(tree[c<<1],tree[c<<1|1]);
	assert(!tree[c].f.empty());
}

node query(int c,int cl,int cr,int l,int r) {
	if (l<=cl and cr<=r) return tree[c];
	int mid=cl+cr>>1;
	if (l<=mid and r<=mid) return query(c<<1,cl,mid,l,r);
	if (r>mid and l>mid) return query(c<<1|1,mid+1,cr,l,r);
	return merge(query(c<<1,cl,mid,l,r),query(c<<1|1,mid+1,cr,l,r));
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
	memset(hmm,-1,sizeof(hmm));
  std::vector<long long> C;
  n = SZ(H);
  rep(i,0,n) h[i] = H[i];
  init(1,0,n-1);
  rep(i,0,SZ(L)) {
	  ll tmp = query(1,0,n-1,L[i],R[i]).mn;
	  C.pb(tmp);
  }
  return C;
}

Compilation message (stderr)

meetings.cpp: In function 'void init(int, int, int)':
meetings.cpp:68:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |  int mid=cl+cr>>1;
      |          ~~^~~
meetings.cpp: In function 'node query(int, int, int, int, int)':
meetings.cpp:77:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |  int mid=cl+cr>>1;
      |          ~~^~~

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