oj.uz

Submission #792237

# Submission time Handle Problem Language Result Execution time Memory
792237 2023-07-24T20:02:38 Z ttamx Meetings (IOI18_meetings) C++14
100 / 100
 2593 ms 530900 KB 
#include "meetings.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> p2;

const int N=750005;
const int K=1<<21;

int n,q;
ll h[N];
int lg[N];
int ql[N],qr[N];
vector<int> qry[N];
vector<ll> ans;
p2 sp[20][N];

struct lichaotree{
	struct line{
		ll m,c;
		line(ll m=0,ll c=1e18):m(m),c(c){}
		ll get(ll x){
			return m*x+c;
		}
	}t[K];
	ll lz[K];
	void pushlz(int l,int r,int i){
		if(!lz[i])return;
		t[i].c+=lz[i];
		if(l<r){
			lz[i*2]+=lz[i];
			lz[i*2+1]+=lz[i];
		}
		lz[i]=0;
	}
	void update(int l,int r,int i,int x,int y,line v){
		pushlz(l,r,i);
		if(y<l||r<x)return;
		int m=(l+r)/2;
		if(x<=l&&r<=y){
			if(v.get(m)<t[i].get(m))swap(t[i],v);
			if(v.get(l)<t[i].get(l))update(l,m,i*2,x,y,v);
			if(v.get(r)<t[i].get(r))update(m+1,r,i*2+1,x,y,v);
		}else{
			update(l,m,i*2,x,y,v);
			update(m+1,r,i*2+1,x,y,v);
		}
	}
	void update(int x,int y,ll m,ll c){
		update(1,n,1,x,y,line(m,c));
	}
	void addval(int l,int r,int i,int x,int y,ll v){
		pushlz(l,r,i);
		if(y<l||r<x)return;
		if(x<=l&&r<=y)return lz[i]+=v,pushlz(l,r,i),void();
		int m=(l+r)/2;
		addval(l,m,i*2,x,y,v);
		addval(m+1,r,i*2+1,x,y,v);
	}
	void addval(int x,int y,ll v){
		addval(1,n,1,x,y,v);
	}
	ll query(int l,int r,int i,int x){
		pushlz(l,r,i);
		ll res=t[i].get(x);
		if(l==r)return res;
		int m=(l+r)/2;
		if(x<=m)return min(res,query(l,m,i*2,x));
		else return min(res,query(m+1,r,i*2+1,x));
	}
	ll query(int x){
		return query(1,n,1,x);
	}
}lctl,lctr;

p2 rmq(int l,int r){
	int k=lg[r-l+1];
	return max(sp[k][l],sp[k][r-(1<<k)+1]);
}

void solve(int l,int r){
	if(l>r)return;
	int m=rmq(l,r).second;
	solve(l,m-1);
	solve(m+1,r);
	lctl.update(m,m,0,0);
	lctr.update(m,m,0,0);
	for(auto i:qry[m]){
		ans[i]=min(lctl.query(ql[i])+h[m]*(qr[i]-m+1),lctr.query(qr[i])+h[m]*(m-ql[i]+1));
	}
	lctl.addval(l,m,h[m]*(r-m+1));
	lctl.update(l,m,-h[m],h[m]*(m+1)+lctl.query(m+1));
	lctr.addval(m,r,h[m]*(m-l+1));
	lctr.update(m,r,h[m],h[m]*(-m+1)+lctr.query(m-1));
}

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
	n=H.size();
	q=L.size();
	ans.resize(q);
	for(int i=1;i<=n;i++){
		h[i]=H[i-1];
		sp[0][i]=p2(h[i],i);
	}
	for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
	for(int i=1;i<=lg[n];i++){
		for(int j=1;j+(1<<i)-1<=n;j++){
			sp[i][j]=max(sp[i-1][j],sp[i-1][j+(1<<(i-1))]);
		}
	}
	for(int i=0;i<q;i++){
		ql[i]=L[i]+1;
		qr[i]=R[i]+1;
		qry[rmq(ql[i],qr[i]).second].emplace_back(i);
	}
	solve(1,n);
	return ans;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 83556 KB Output is correct
2 Correct 35 ms 84280 KB Output is correct
3 Correct 34 ms 84400 KB Output is correct
4 Correct 34 ms 84404 KB Output is correct
5 Correct 34 ms 84360 KB Output is correct
6 Correct 34 ms 84564 KB Output is correct
7 Correct 34 ms 84388 KB Output is correct
8 Correct 40 ms 84616 KB Output is correct
9 Correct 35 ms 84664 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 83556 KB Output is correct
2 Correct 35 ms 84280 KB Output is correct
3 Correct 34 ms 84400 KB Output is correct
4 Correct 34 ms 84404 KB Output is correct
5 Correct 34 ms 84360 KB Output is correct
6 Correct 34 ms 84564 KB Output is correct
7 Correct 34 ms 84388 KB Output is correct
8 Correct 40 ms 84616 KB Output is correct
9 Correct 35 ms 84664 KB Output is correct
10 Correct 38 ms 85256 KB Output is correct
11 Correct 37 ms 85256 KB Output is correct
12 Correct 40 ms 85348 KB Output is correct
13 Correct 37 ms 85356 KB Output is correct
14 Correct 40 ms 85748 KB Output is correct
15 Correct 40 ms 85256 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 83540 KB Output is correct
2 Correct 66 ms 88652 KB Output is correct
3 Correct 234 ms 129160 KB Output is correct
4 Correct 216 ms 120988 KB Output is correct
5 Correct 227 ms 131068 KB Output is correct
6 Correct 215 ms 131664 KB Output is correct
7 Correct 228 ms 132980 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 83540 KB Output is correct
2 Correct 66 ms 88652 KB Output is correct
3 Correct 234 ms 129160 KB Output is correct
4 Correct 216 ms 120988 KB Output is correct
5 Correct 227 ms 131068 KB Output is correct
6 Correct 215 ms 131664 KB Output is correct
7 Correct 228 ms 132980 KB Output is correct
8 Correct 215 ms 121780 KB Output is correct
9 Correct 197 ms 121600 KB Output is correct
10 Correct 198 ms 121748 KB Output is correct
11 Correct 213 ms 120968 KB Output is correct
12 Correct 193 ms 120856 KB Output is correct
13 Correct 202 ms 120972 KB Output is correct
14 Correct 231 ms 128948 KB Output is correct
15 Correct 204 ms 120724 KB Output is correct
16 Correct 236 ms 129688 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 83556 KB Output is correct
2 Correct 35 ms 84280 KB Output is correct
3 Correct 34 ms 84400 KB Output is correct
4 Correct 34 ms 84404 KB Output is correct
5 Correct 34 ms 84360 KB Output is correct
6 Correct 34 ms 84564 KB Output is correct
7 Correct 34 ms 84388 KB Output is correct
8 Correct 40 ms 84616 KB Output is correct
9 Correct 35 ms 84664 KB Output is correct
10 Correct 38 ms 85256 KB Output is correct
11 Correct 37 ms 85256 KB Output is correct
12 Correct 40 ms 85348 KB Output is correct
13 Correct 37 ms 85356 KB Output is correct
14 Correct 40 ms 85748 KB Output is correct
15 Correct 40 ms 85256 KB Output is correct
16 Correct 32 ms 83540 KB Output is correct
17 Correct 66 ms 88652 KB Output is correct
18 Correct 234 ms 129160 KB Output is correct
19 Correct 216 ms 120988 KB Output is correct
20 Correct 227 ms 131068 KB Output is correct
21 Correct 215 ms 131664 KB Output is correct
22 Correct 228 ms 132980 KB Output is correct
23 Correct 215 ms 121780 KB Output is correct
24 Correct 197 ms 121600 KB Output is correct
25 Correct 198 ms 121748 KB Output is correct
26 Correct 213 ms 120968 KB Output is correct
27 Correct 193 ms 120856 KB Output is correct
28 Correct 202 ms 120972 KB Output is correct
29 Correct 231 ms 128948 KB Output is correct
30 Correct 204 ms 120724 KB Output is correct
31 Correct 236 ms 129688 KB Output is correct
32 Correct 2231 ms 403328 KB Output is correct
33 Correct 1438 ms 403652 KB Output is correct
34 Correct 1549 ms 404208 KB Output is correct
35 Correct 1863 ms 405372 KB Output is correct
36 Correct 1428 ms 404476 KB Output is correct
37 Correct 1614 ms 404308 KB Output is correct
38 Correct 2321 ms 466596 KB Output is correct
39 Correct 2123 ms 466800 KB Output is correct
40 Correct 1879 ms 412024 KB Output is correct
41 Correct 2484 ms 527184 KB Output is correct
42 Correct 2593 ms 530900 KB Output is correct
43 Correct 2568 ms 530792 KB Output is correct
44 Correct 2404 ms 468484 KB Output is correct