oj.uz

Submission #748800

# Submission time Handle Problem Language Result Execution time Memory
748800 2023-05-27T03:18:51 Z vjudge1 Meetings (IOI18_meetings) C++14
100 / 100
 3821 ms 573772 KB 
#include"meetings.h"
#define N 750009
#define LG 20
#define lc(i) ((i)<<1|1)
#define rc(i) ((i)+1<<1)
#define int long long
using namespace std;
int n,q,a[N],lg[N],st[LG][N],trek[N<<2],treb[N<<2],lazy[N<<2];
int lft[N<<2],rgt[N<<2];
vector<int>ql[N],qr[N],id[N],ans;
inline int qmx(const int&l,const int&r)
{
	int i=lg[r-l];
	if(a[st[i][l]]>a[st[i][r-(1<<i)+1]])return st[i][l];
	else return st[i][r-(1<<i)+1];
}
inline void pd(const int&i,const int&l,const int&r)
{
	if(trek[i]^1<<30)
	{
		int mid=l+r>>1;
		trek[lc(i)]=trek[rc(i)]=trek[i];
		treb[lc(i)]=treb[rc(i)]=treb[i];
		lazy[lc(i)]=lazy[rc(i)]=0;
		lft[lc(i)]=trek[i]*l+treb[i];
		rgt[lc(i)]=trek[i]*mid+treb[i];
		lft[rc(i)]=trek[i]*(mid+1)+treb[i];
		rgt[rc(i)]=trek[i]*r+treb[i];
		trek[i]=1<<30;
	}
	if(lazy[i])
	{
		lazy[lc(i)]+=lazy[i];
		lazy[rc(i)]+=lazy[i];
		lft[lc(i)]+=lazy[i];
		rgt[lc(i)]+=lazy[i];
		lft[rc(i)]+=lazy[i];
		rgt[rc(i)]+=lazy[i];
		lazy[i]=0;
	}
}
inline void push(const int&i,const int&l,const int&r,const int&ql,
	const int&qr,const int&k,const int&b)
{
	if(qr<l||r<ql)return;
	if(ql<=l&&r<=qr)
	{
		trek[i]=k;treb[i]=b;lazy[i]=0;
		lft[i]=k*l+b;
		rgt[i]=k*r+b;
		return;
	}
	int mid=l+r>>1;pd(i,l,r);
	push(lc(i),l,mid,ql,qr,k,b);
	push(rc(i),mid+1,r,ql,qr,k,b);
	lft[i]=lft[lc(i)];rgt[i]=rgt[rc(i)];
}
inline int qry(const int&i,const int&l,const int&r,const int&p)
{
	if(l==r)return lft[i];
	int mid=l+r>>1;pd(i,l,r);
	if(p<=mid)return qry(lc(i),l,mid,p);
	return qry(rc(i),mid+1,r,p);
}
inline void add(const int&i,const int&l,const int&r,const int&ql,
	const int&qr,const int&x)
{
	if(qr<l||r<ql)return;
	if(ql<=l&&r<=qr){lazy[i]+=x;lft[i]+=x;rgt[i]+=x;return;}
	int mid=l+r>>1;pd(i,l,r);
	add(lc(i),l,mid,ql,qr,x);add(rc(i),mid+1,r,ql,qr,x);
	lft[i]=lft[lc(i)];rgt[i]=rgt[rc(i)];
}
inline int find(const int&i,const int&l,const int&r,const int&ql,
	const int&qr,const int&k,const int&b,const bool&dir)
{
	if(qr<l||r<ql)return-1;
	if(!dir)
	{
		if(qr>=r&&rgt[i]<=k*r+b)return-1;
		if(ql<=l&&lft[i]>k*l+b)return l;
		int mid=l+r>>1;pd(i,l,r);
		int tmp=find(lc(i),l,mid,ql,qr,k,b,0);
		if(~tmp)return tmp;
		return find(rc(i),mid+1,r,ql,qr,k,b,0);
	}
	else
	{
		if(ql<=l&&lft[i]<=k*l+b)return-1;
		if(qr>=r&&rgt[i]>k*r+b)return r;
		int mid=l+r>>1;pd(i,l,r);
		int tmp=find(rc(i),mid+1,r,ql,qr,k,b,1);
		if(~tmp)return tmp;
		return find(lc(i),l,mid,ql,qr,k,b,1);
	}
}
inline void dfs1(const int&l,const int&r)
{
	if(l==r){push(0,0,n-1,l,l,0,a[l]);return;}
	int i=qmx(l,r);
	if(i==l)
	{
		dfs1(i+1,r);
		push(0,0,n-1,i,i,0,qry(0,0,n-1,i+1)+a[i]);
		for(int j=0;j<ql[i].size();++j)
			ans[id[i][j]]=min(ans[id[i][j]],a[i]*(qr[i][j]-i+1));
		return;
	}
	if(i==r)
	{
		dfs1(l,i-1);
		push(0,0,n-1,i,i,0,0);
		for(int j=0;j<ql[i].size();++j)
			ans[id[i][j]]=min(ans[id[i][j]],qry(0,0,n-1,ql[i][j])+a[i]);
		add(0,0,n-1,l,i,a[i]);
		return;
	}
	dfs1(l,i-1);dfs1(i+1,r);
	push(0,0,n-1,i,i,0,0);
	for(int j=0;j<ql[i].size();++j)
		ans[id[i][j]]=min(ans[id[i][j]],
			qry(0,0,n-1,ql[i][j])+a[i]*(qr[i][j]-i+1));
	push(0,0,n-1,i,i,0,qry(0,0,n-1,i+1)+a[i]);
	add(0,0,n-1,l,i-1,a[i]*(r-i+1));
	int k=-a[i],b=qry(0,0,n-1,i)+a[i]*i;
	int x=find(0,0,n-1,l,i-1,k,b,0);
	if(~x)push(0,0,n-1,x,i-1,k,b);
}
inline void dfs2(const int&l,const int&r)
{
	if(l==r){push(0,0,n-1,l,l,0,a[l]);return;}
	int i=qmx(l,r);
	if(i==l)
	{
		dfs2(i+1,r);
		push(0,0,n-1,i,i,0,0);
		for(int j=0;j<ql[i].size();++j)
			ans[id[i][j]]=min(ans[id[i][j]],qry(0,0,n-1,qr[i][j])+a[i]);
		add(0,0,n-1,i,r,a[i]);
		return;
	}
	if(i==r)
	{
		dfs2(l,i-1);
		push(0,0,n-1,i,i,0,qry(0,0,n-1,i-1)+a[i]);
		for(int j=0;j<ql[i].size();++j)
			ans[id[i][j]]=min(ans[id[i][j]],a[i]*(i-ql[i][j]+1));
		return;
	}
	dfs2(l,i-1);dfs2(i+1,r);
	push(0,0,n-1,i,i,0,0);
	for(int j=0;j<ql[i].size();++j)
		ans[id[i][j]]=min(ans[id[i][j]],
			qry(0,0,n-1,qr[i][j])+a[i]*(i-ql[i][j]+1));
	push(0,0,n-1,i,i,0,qry(0,0,n-1,i-1)+a[i]);
	add(0,0,n-1,i+1,r,a[i]*(i-l+1));
	int k=a[i],b=qry(0,0,n-1,i)-a[i]*i;
	int x=find(0,0,n-1,i+1,r,k,b,1);
	if(~x)push(0,0,n-1,i+1,x,k,b);
}
vector<int>minimum_costs(vector<signed>H,vector<signed>L,vector<signed>R)
{
	n=H.size();q=L.size();ans.resize(q);
	for(int i=0;i<n;a[i]=H[i],++i);
	for(int i=2;i<n;lg[i]=lg[i>>1]+1,++i);
	for(int i=n-1;i>=0;--i)
	{
		st[0][i]=i;
		for(int j=1;j<LG;++j)
			if(i+(1<<j-1)<n)
				if(a[st[j-1][i]]>a[st[j-1][i+(1<<j-1)]])
					st[j][i]=st[j-1][i];
				else st[j][i]=st[j-1][i+(1<<j-1)];
			else st[j][i]=st[j-1][i];
	}
	for(int i=0,u,v,w;i<q;++i)
	{
		u=L[i],v=R[i],w=qmx(u,v);
		if(u==v){ans[i]=a[u];continue;}
		ql[w].emplace_back(u),qr[w].emplace_back(v),
		id[w].emplace_back(i);ans[i]=1ll<<60;
	}
	for(int i=0;i<N<<2;trek[i++]=1<<30);
	dfs1(0,n-1);
	for(int i=0;i<N<<2;trek[i++]=1<<30);
	dfs2(0,n-1);
	return ans;
}

Compilation message

meetings.cpp: In function 'void pd(const long long int&, const long long int&, const long long int&)':
meetings.cpp:21:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |   int mid=l+r>>1;
      |           ~^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    5 | #define rc(i) ((i)+1<<1)
      |                ~~~^~
meetings.cpp:22:20: note: in expansion of macro 'rc'
   22 |   trek[lc(i)]=trek[rc(i)]=trek[i];
      |                    ^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    5 | #define rc(i) ((i)+1<<1)
      |                ~~~^~
meetings.cpp:23:20: note: in expansion of macro 'rc'
   23 |   treb[lc(i)]=treb[rc(i)]=treb[i];
      |                    ^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    5 | #define rc(i) ((i)+1<<1)
      |                ~~~^~
meetings.cpp:24:20: note: in expansion of macro 'rc'
   24 |   lazy[lc(i)]=lazy[rc(i)]=0;
      |                    ^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    5 | #define rc(i) ((i)+1<<1)
      |                ~~~^~
meetings.cpp:27:7: note: in expansion of macro 'rc'
   27 |   lft[rc(i)]=trek[i]*(mid+1)+treb[i];
      |       ^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    5 | #define rc(i) ((i)+1<<1)
      |                ~~~^~
meetings.cpp:28:7: note: in expansion of macro 'rc'
   28 |   rgt[rc(i)]=trek[i]*r+treb[i];
      |       ^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    5 | #define rc(i) ((i)+1<<1)
      |                ~~~^~
meetings.cpp:34:8: note: in expansion of macro 'rc'
   34 |   lazy[rc(i)]+=lazy[i];
      |        ^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    5 | #define rc(i) ((i)+1<<1)
      |                ~~~^~
meetings.cpp:37:7: note: in expansion of macro 'rc'
   37 |   lft[rc(i)]+=lazy[i];
      |       ^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    5 | #define rc(i) ((i)+1<<1)
      |                ~~~^~
meetings.cpp:38:7: note: in expansion of macro 'rc'
   38 |   rgt[rc(i)]+=lazy[i];
      |       ^~
meetings.cpp: In function 'void push(const long long int&, const long long int&, const long long int&, const long long int&, const long long int&, const long long int&, const long long int&)':
meetings.cpp:53:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |  int mid=l+r>>1;pd(i,l,r);
      |          ~^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    5 | #define rc(i) ((i)+1<<1)
      |                ~~~^~
meetings.cpp:55:7: note: in expansion of macro 'rc'
   55 |  push(rc(i),mid+1,r,ql,qr,k,b);
      |       ^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    5 | #define rc(i) ((i)+1<<1)
      |                ~~~^~
meetings.cpp:56:31: note: in expansion of macro 'rc'
   56 |  lft[i]=lft[lc(i)];rgt[i]=rgt[rc(i)];
      |                               ^~
meetings.cpp: In function 'long long int qry(const long long int&, const long long int&, const long long int&, const long long int&)':
meetings.cpp:61:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |  int mid=l+r>>1;pd(i,l,r);
      |          ~^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    5 | #define rc(i) ((i)+1<<1)
      |                ~~~^~
meetings.cpp:63:13: note: in expansion of macro 'rc'
   63 |  return qry(rc(i),mid+1,r,p);
      |             ^~
meetings.cpp: In function 'void add(const long long int&, const long long int&, const long long int&, const long long int&, const long long int&, const long long int&)':
meetings.cpp:70:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |  int mid=l+r>>1;pd(i,l,r);
      |          ~^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    5 | #define rc(i) ((i)+1<<1)
      |                ~~~^~
meetings.cpp:71:31: note: in expansion of macro 'rc'
   71 |  add(lc(i),l,mid,ql,qr,x);add(rc(i),mid+1,r,ql,qr,x);
      |                               ^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    5 | #define rc(i) ((i)+1<<1)
      |                ~~~^~
meetings.cpp:72:31: note: in expansion of macro 'rc'
   72 |  lft[i]=lft[lc(i)];rgt[i]=rgt[rc(i)];
      |                               ^~
meetings.cpp: In function 'long long int find(const long long int&, const long long int&, const long long int&, const long long int&, const long long int&, const long long int&, const long long int&, const bool&)':
meetings.cpp:82:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |   int mid=l+r>>1;pd(i,l,r);
      |           ~^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    5 | #define rc(i) ((i)+1<<1)
      |                ~~~^~
meetings.cpp:85:15: note: in expansion of macro 'rc'
   85 |   return find(rc(i),mid+1,r,ql,qr,k,b,0);
      |               ^~
meetings.cpp:91:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |   int mid=l+r>>1;pd(i,l,r);
      |           ~^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    5 | #define rc(i) ((i)+1<<1)
      |                ~~~^~
meetings.cpp:92:16: note: in expansion of macro 'rc'
   92 |   int tmp=find(rc(i),mid+1,r,ql,qr,k,b,1);
      |                ^~
meetings.cpp: In function 'void dfs1(const long long int&, const long long int&)':
meetings.cpp:105:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |   for(int j=0;j<ql[i].size();++j)
      |               ~^~~~~~~~~~~~~
meetings.cpp:113:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |   for(int j=0;j<ql[i].size();++j)
      |               ~^~~~~~~~~~~~~
meetings.cpp:120:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |  for(int j=0;j<ql[i].size();++j)
      |              ~^~~~~~~~~~~~~
meetings.cpp: In function 'void dfs2(const long long int&, const long long int&)':
meetings.cpp:137:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |   for(int j=0;j<ql[i].size();++j)
      |               ~^~~~~~~~~~~~~
meetings.cpp:146:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |   for(int j=0;j<ql[i].size();++j)
      |               ~^~~~~~~~~~~~~
meetings.cpp:152:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |  for(int j=0;j<ql[i].size();++j)
      |              ~^~~~~~~~~~~~~
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:170:14: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  170 |    if(i+(1<<j-1)<n)
      |             ~^~
meetings.cpp:171:39: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  171 |     if(a[st[j-1][i]]>a[st[j-1][i+(1<<j-1)]])
      |                                      ~^~
meetings.cpp:173:34: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  173 |     else st[j][i]=st[j-1][i+(1<<j-1)];
      |                                 ~^~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 76756 KB Output is correct
2 Correct 43 ms 77628 KB Output is correct
3 Correct 44 ms 77588 KB Output is correct
4 Correct 50 ms 77612 KB Output is correct
5 Correct 41 ms 77504 KB Output is correct
6 Correct 42 ms 78016 KB Output is correct
7 Correct 43 ms 77636 KB Output is correct
8 Correct 40 ms 78108 KB Output is correct
9 Correct 40 ms 77852 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 76756 KB Output is correct
2 Correct 43 ms 77628 KB Output is correct
3 Correct 44 ms 77588 KB Output is correct
4 Correct 50 ms 77612 KB Output is correct
5 Correct 41 ms 77504 KB Output is correct
6 Correct 42 ms 78016 KB Output is correct
7 Correct 43 ms 77636 KB Output is correct
8 Correct 40 ms 78108 KB Output is correct
9 Correct 40 ms 77852 KB Output is correct
10 Correct 49 ms 78668 KB Output is correct
11 Correct 48 ms 78668 KB Output is correct
12 Correct 50 ms 78624 KB Output is correct
13 Correct 47 ms 78696 KB Output is correct
14 Correct 50 ms 79436 KB Output is correct
15 Correct 49 ms 78660 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 76748 KB Output is correct
2 Correct 95 ms 84112 KB Output is correct
3 Correct 389 ms 127144 KB Output is correct
4 Correct 265 ms 111916 KB Output is correct
5 Correct 242 ms 122232 KB Output is correct
6 Correct 309 ms 132428 KB Output is correct
7 Correct 322 ms 134172 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 76748 KB Output is correct
2 Correct 95 ms 84112 KB Output is correct
3 Correct 389 ms 127144 KB Output is correct
4 Correct 265 ms 111916 KB Output is correct
5 Correct 242 ms 122232 KB Output is correct
6 Correct 309 ms 132428 KB Output is correct
7 Correct 322 ms 134172 KB Output is correct
8 Correct 363 ms 113224 KB Output is correct
9 Correct 293 ms 112768 KB Output is correct
10 Correct 301 ms 113280 KB Output is correct
11 Correct 325 ms 111708 KB Output is correct
12 Correct 289 ms 111052 KB Output is correct
13 Correct 288 ms 112340 KB Output is correct
14 Correct 424 ms 127228 KB Output is correct
15 Correct 323 ms 110956 KB Output is correct
16 Correct 302 ms 127260 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 76756 KB Output is correct
2 Correct 43 ms 77628 KB Output is correct
3 Correct 44 ms 77588 KB Output is correct
4 Correct 50 ms 77612 KB Output is correct
5 Correct 41 ms 77504 KB Output is correct
6 Correct 42 ms 78016 KB Output is correct
7 Correct 43 ms 77636 KB Output is correct
8 Correct 40 ms 78108 KB Output is correct
9 Correct 40 ms 77852 KB Output is correct
10 Correct 49 ms 78668 KB Output is correct
11 Correct 48 ms 78668 KB Output is correct
12 Correct 50 ms 78624 KB Output is correct
13 Correct 47 ms 78696 KB Output is correct
14 Correct 50 ms 79436 KB Output is correct
15 Correct 49 ms 78660 KB Output is correct
16 Correct 39 ms 76748 KB Output is correct
17 Correct 95 ms 84112 KB Output is correct
18 Correct 389 ms 127144 KB Output is correct
19 Correct 265 ms 111916 KB Output is correct
20 Correct 242 ms 122232 KB Output is correct
21 Correct 309 ms 132428 KB Output is correct
22 Correct 322 ms 134172 KB Output is correct
23 Correct 363 ms 113224 KB Output is correct
24 Correct 293 ms 112768 KB Output is correct
25 Correct 301 ms 113280 KB Output is correct
26 Correct 325 ms 111708 KB Output is correct
27 Correct 289 ms 111052 KB Output is correct
28 Correct 288 ms 112340 KB Output is correct
29 Correct 424 ms 127228 KB Output is correct
30 Correct 323 ms 110956 KB Output is correct
31 Correct 302 ms 127260 KB Output is correct
32 Correct 2555 ms 342324 KB Output is correct
33 Correct 2079 ms 340552 KB Output is correct
34 Correct 2374 ms 351576 KB Output is correct
35 Correct 2737 ms 348496 KB Output is correct
36 Correct 1980 ms 342172 KB Output is correct
37 Correct 2293 ms 351928 KB Output is correct
38 Correct 3515 ms 465908 KB Output is correct
39 Correct 3821 ms 465876 KB Output is correct
40 Correct 2646 ms 362672 KB Output is correct
41 Correct 2863 ms 569868 KB Output is correct
42 Correct 3184 ms 573772 KB Output is correct
43 Correct 3170 ms 573712 KB Output is correct
44 Correct 3732 ms 465248 KB Output is correct