oj.uz

Submission #159115

# Submission time Handle Problem Language Result Execution time Memory
159115 2019-10-21T02:30:24 Z kig9981 Meetings (IOI18_meetings) C++17
100 / 100
 3257 ms 324328 KB 
#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;

struct lichao
{
	int A, l, r;
	long long B, lazy;
	lichao() : A(0), l(0), r(0), B(0x3fffffffffffffffLL), lazy(0) {}
};

const int SZ=1<<20;
pair<int,int> Mtree[2*SZ];
lichao ltree[2*SZ], rtree[2*SZ];
vector<long long> res;
vector<tuple<int,int,int>> Q[750001];

pair<int,int> get_max(int s, int e)
{
	pair<int,int> ret(-1,-1);
	for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
		if(s&1) ret=max(ret,Mtree[s++]);
		if(~e&1) ret=max(ret,Mtree[e--]);
	}
	return ret;
}

void lazy_propagation(lichao *tree, int bit, int s, int e)
{
	if(tree[bit].lazy) {
		tree[bit].B+=tree[bit].lazy;
		if(s<e) {
			tree[2*bit].lazy+=tree[bit].lazy;
			tree[2*bit+1].lazy+=tree[bit].lazy;
		}
		tree[bit].lazy=0;
	}
}

int get_sign(long long a)
{
	return a<0 ? -1:a>0;
}

void add_line(lichao *tree, int n1, int n2, int A, long long B, int bit=1, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	lazy_propagation(tree,bit,s,e);
	if(n2<n1 || n2<s || e<n1) return;
	if(n1<=s && e<=n2) {
		int &pA=tree[bit].A;
		long long &pB=tree[bit].B, ys=1LL*A*s+B, ym=1LL*A*m+B, ye=1LL*A*e+B, pys=1LL*pA*s+pB, pym=1LL*pA*m+pB, pye=1LL*pA*e+pB;
		if(ym<pym) {
			swap(pA,A); swap(pB,B);
			swap(pys,ys); swap(pym,ym); swap(pye,ye);
		}
		if(pys<=ys && pye<=ye) return;
		if(get_sign(ys-pys)*get_sign(ym-pym)<0 || ym==pym && ys<pys) add_line(tree,n1,n2,A,B,2*bit,s,m);
		else add_line(tree,n1,n2,A,B,2*bit+1,m+1,e);
		return;
	}
	add_line(tree,n1,n2,A,B,2*bit,s,m);
	add_line(tree,n1,n2,A,B,2*bit+1,m+1,e);
}

void add_tree(lichao *tree, int n1, int n2, long long v, int bit=1, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	lazy_propagation(tree,bit,s,e);
	if(n2<n1 || n2<s || e<n1) return;
	if(n1<=s && e<=n2) {
		tree[bit].lazy=v;
		lazy_propagation(tree,bit,s,e);
		return;
	}
	add_tree(tree,n1,n2,v,2*bit,s,m);
	add_tree(tree,n1,n2,v,2*bit+1,m+1,e);
}

long long get_y(lichao *tree, int x, int bit=1, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	lazy_propagation(tree,bit,s,e);
	if(s==e) return 1LL*tree[bit].A*x+tree[bit].B;
	return min(x<=m ? get_y(tree,x,2*bit,s,m):get_y(tree,x,2*bit+1,m+1,e),1LL*tree[bit].A*x+tree[bit].B);
}

void solve(int s, int e)
{
	if(s>e) return;
	auto[M,m]=get_max(s,e);
	solve(s,m-1);
	solve(m+1,e);
	for(auto[l,r,i]: Q[m]) res[i]=min(get_y(ltree,l)+(r-m+1LL)*M,get_y(rtree,r)+(m-l+1LL)*M);
	add_tree(ltree,s,m-1,(e-m+1LL)*M);
	add_line(ltree,s,m,-M,(m<e ? get_y(ltree,m+1):0)+M*(m+1LL));
	add_tree(rtree,m+1,e,(m-s+1LL)*M);
	add_line(rtree,m,e,M,(s<m ? get_y(rtree,m-1):0)+M*(1LL-m));
}

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R)
{
	int N=H.size(), M=L.size();
	res.resize(M);
	for(int i=0;i<N;i++) Mtree[SZ+i+1]={H[i],i+1};
	for(int i=SZ;--i;) Mtree[i]=max(Mtree[2*i],Mtree[2*i+1]);
	for(int i=0;i<M;i++) {
		if(++L[i]<++R[i]) Q[get_max(L[i],R[i]).second].emplace_back(L[i],R[i],i);
		else res[i]=H[L[i]-1];
	}
	solve(1,N);
	return res;
}

Compilation message

meetings.cpp: In function 'void add_line(lichao*, int, int, int, long long int, int, int, int)':
meetings.cpp:59:53: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if(get_sign(ys-pys)*get_sign(ym-pym)<0 || ym==pym && ys<pys) add_line(tree,n1,n2,A,B,2*bit,s,m);
                                             ~~~~~~~~^~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 157560 KB Output is correct
2 Correct 141 ms 157532 KB Output is correct
3 Correct 149 ms 157564 KB Output is correct
4 Correct 141 ms 157560 KB Output is correct
5 Correct 142 ms 157560 KB Output is correct
6 Correct 141 ms 157708 KB Output is correct
7 Correct 159 ms 157568 KB Output is correct
8 Correct 143 ms 157816 KB Output is correct
9 Correct 142 ms 157852 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 157560 KB Output is correct
2 Correct 141 ms 157532 KB Output is correct
3 Correct 149 ms 157564 KB Output is correct
4 Correct 141 ms 157560 KB Output is correct
5 Correct 142 ms 157560 KB Output is correct
6 Correct 141 ms 157708 KB Output is correct
7 Correct 159 ms 157568 KB Output is correct
8 Correct 143 ms 157816 KB Output is correct
9 Correct 142 ms 157852 KB Output is correct
10 Correct 152 ms 158044 KB Output is correct
11 Correct 150 ms 157948 KB Output is correct
12 Correct 150 ms 158072 KB Output is correct
13 Correct 150 ms 158072 KB Output is correct
14 Correct 151 ms 158352 KB Output is correct
15 Correct 149 ms 158096 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 157560 KB Output is correct
2 Correct 206 ms 161424 KB Output is correct
3 Correct 453 ms 172408 KB Output is correct
4 Correct 412 ms 166012 KB Output is correct
5 Correct 348 ms 170488 KB Output is correct
6 Correct 452 ms 174256 KB Output is correct
7 Correct 478 ms 175668 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 157560 KB Output is correct
2 Correct 206 ms 161424 KB Output is correct
3 Correct 453 ms 172408 KB Output is correct
4 Correct 412 ms 166012 KB Output is correct
5 Correct 348 ms 170488 KB Output is correct
6 Correct 452 ms 174256 KB Output is correct
7 Correct 478 ms 175668 KB Output is correct
8 Correct 421 ms 166736 KB Output is correct
9 Correct 378 ms 166360 KB Output is correct
10 Correct 401 ms 166776 KB Output is correct
11 Correct 415 ms 165868 KB Output is correct
12 Correct 376 ms 165820 KB Output is correct
13 Correct 390 ms 166328 KB Output is correct
14 Correct 448 ms 172408 KB Output is correct
15 Correct 395 ms 165680 KB Output is correct
16 Correct 452 ms 172636 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 157560 KB Output is correct
2 Correct 141 ms 157532 KB Output is correct
3 Correct 149 ms 157564 KB Output is correct
4 Correct 141 ms 157560 KB Output is correct
5 Correct 142 ms 157560 KB Output is correct
6 Correct 141 ms 157708 KB Output is correct
7 Correct 159 ms 157568 KB Output is correct
8 Correct 143 ms 157816 KB Output is correct
9 Correct 142 ms 157852 KB Output is correct
10 Correct 152 ms 158044 KB Output is correct
11 Correct 150 ms 157948 KB Output is correct
12 Correct 150 ms 158072 KB Output is correct
13 Correct 150 ms 158072 KB Output is correct
14 Correct 151 ms 158352 KB Output is correct
15 Correct 149 ms 158096 KB Output is correct
16 Correct 135 ms 157560 KB Output is correct
17 Correct 206 ms 161424 KB Output is correct
18 Correct 453 ms 172408 KB Output is correct
19 Correct 412 ms 166012 KB Output is correct
20 Correct 348 ms 170488 KB Output is correct
21 Correct 452 ms 174256 KB Output is correct
22 Correct 478 ms 175668 KB Output is correct
23 Correct 421 ms 166736 KB Output is correct
24 Correct 378 ms 166360 KB Output is correct
25 Correct 401 ms 166776 KB Output is correct
26 Correct 415 ms 165868 KB Output is correct
27 Correct 376 ms 165820 KB Output is correct
28 Correct 390 ms 166328 KB Output is correct
29 Correct 448 ms 172408 KB Output is correct
30 Correct 395 ms 165680 KB Output is correct
31 Correct 452 ms 172636 KB Output is correct
32 Correct 2563 ms 224464 KB Output is correct
33 Correct 2037 ms 223392 KB Output is correct
34 Correct 2266 ms 227120 KB Output is correct
35 Correct 2597 ms 227220 KB Output is correct
36 Correct 2036 ms 225260 KB Output is correct
37 Correct 2184 ms 227676 KB Output is correct
38 Correct 3042 ms 276696 KB Output is correct
39 Correct 2986 ms 276468 KB Output is correct
40 Correct 2468 ms 234100 KB Output is correct
41 Correct 2975 ms 321284 KB Output is correct
42 Correct 3210 ms 324328 KB Output is correct
43 Correct 3257 ms 324064 KB Output is correct
44 Correct 2952 ms 276268 KB Output is correct