oj.uz

Submission #741709

# Submission time Handle Problem Language Result Execution time Memory
741709 2023-05-14T16:03:10 Z myrcella Meetings (IOI18_meetings) C++17
41 / 100
 1293 ms 559204 KB 
//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

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.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 275812 KB Output is correct
2 Runtime error 334 ms 559204 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 275812 KB Output is correct
2 Runtime error 334 ms 559204 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 275844 KB Output is correct
2 Correct 358 ms 278192 KB Output is correct
3 Correct 815 ms 288600 KB Output is correct
4 Correct 824 ms 287292 KB Output is correct
5 Correct 273 ms 288612 KB Output is correct
6 Correct 664 ms 287348 KB Output is correct
7 Correct 724 ms 287432 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 275844 KB Output is correct
2 Correct 358 ms 278192 KB Output is correct
3 Correct 815 ms 288600 KB Output is correct
4 Correct 824 ms 287292 KB Output is correct
5 Correct 273 ms 288612 KB Output is correct
6 Correct 664 ms 287348 KB Output is correct
7 Correct 724 ms 287432 KB Output is correct
8 Correct 1049 ms 291332 KB Output is correct
9 Correct 1111 ms 292160 KB Output is correct
10 Correct 772 ms 292068 KB Output is correct
11 Correct 1052 ms 292240 KB Output is correct
12 Correct 1293 ms 292240 KB Output is correct
13 Correct 807 ms 292180 KB Output is correct
14 Correct 827 ms 289960 KB Output is correct
15 Correct 1149 ms 292156 KB Output is correct
16 Correct 913 ms 288000 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 275812 KB Output is correct
2 Runtime error 334 ms 559204 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -