oj.uz

답안 #558711

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
558711 2022-05-08T06:31:45 Z jamezzz 모임들 (IOI18_meetings) C++17
100 / 100
 3032 ms 386092 KB 
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> line;
typedef pair<int,int> ii;
#define fi first
#define se second
#define lc 2*i+1
#define rc 2*i+2
#define pb push_back
#define LINF 1023456789123456789

#define pf printf

#define maxn 750005

int n,q;
vector<int> h;
vector<ll> ans;

struct query{
	int l,r,i;
};
vector<query> qrys[maxn];

ll eval(line l,ll x){
	return l.fi*x+l.se;
}

struct seg{
	ii v[maxn*4];
	void init(int i,int s,int e){
		if(s==e){v[i]={h[s],s};return;}
		int m=(s+e)>>1;
		init(lc,s,m);
		init(rc,m+1,e);
		v[i]=max(v[lc],v[rc]);
	}
	void init(){
		init(0,0,n-1);
	}
	ii qry(int i,int s,int e,int x,int y){
		if(s==x&&e==y)return v[i];
		int m=(s+e)>>1;
		if(y<=m)return qry(lc,s,m,x,y);
		if(x>m)return qry(rc,m+1,e,x,y);
		return max(qry(lc,s,m,x,m),qry(rc,m+1,e,m+1,y));
	}
	int qry(int x,int y){
		return qry(0,0,n-1,x,y).se;
	}
}maxseg;

struct lichao{
	int s,e,m;
	lichao *l,*r;
	line val={0,LINF};
	ll lz=0;
	
	lichao(int _s,int _e){
		s=_s;e=_e;m=(s+e)>>1;
		if(s!=e){
			l=new lichao(s,m);
			r=new lichao(m+1,e);
		}
	}
	void ppo(){
		val.se+=lz;
		if(s!=e)l->lz+=lz,r->lz+=lz;
		lz=0;
	}
	void insert(int x,int y,line v){
		if(x>y)return;
		ppo();
		if(s==x&&e==y){
			if(eval(v,m)<eval(val,m))swap(v,val);
			if(s==e)return;
			if(eval(v,s)>=eval(val,s)&&eval(v,e)>=eval(val,e))return;
			if(eval(v,s)<eval(val,s))l->insert(x,m,v);
			else r->insert(m+1,y,v);
		}
		if(y<=m)l->insert(x,y,v);
		else if(x>m)r->insert(x,y,v);
		else l->insert(x,m,v),r->insert(m+1,y,v);
	}
	void add(int x,int y,ll v){
		if(x>y)return;
		if(s==x&&e==y){lz+=v;return;}
		if(y<=m)l->add(x,y,v);
		else if(x>m)r->add(x,y,v);
		else l->add(x,m,v),r->add(m+1,y,v);
	}
	ll qry(int x){
		ppo();
		if(s==x&&e==x)return eval(val,x);
		if(x<=m)return min(eval(val,x),l->qry(x));
		else return min(eval(val,x),r->qry(x));
	}
}*llct,*rlct;

void solve(int l,int r){
	if(l>r)return;
	int m=maxseg.qry(l,r);
	solve(l,m-1);
	solve(m+1,r);
	
	llct->insert(m,m,{0,0});
	rlct->insert(m,m,{0,0});
	
	for(query &q:qrys[m]){
		ans[q.i]=min(llct->qry(q.l)+(ll)(q.r-m+1)*h[m],
					 rlct->qry(q.r)+(ll)(m-q.l+1)*h[m]);
	}
	
	llct->add(l,m,(ll)(r-m+1)*h[m]);
	llct->insert(l,m,{-h[m],(ll)(m+1)*h[m]+(m==r?0:llct->qry(m+1))});
	
	rlct->add(m,r,(ll)(m-l+1)*h[m]);
	rlct->insert(m,r,{h[m],(ll)(1-m)*h[m]+(l==m?0:rlct->qry(m-1))});
}

vector<ll> minimum_costs(vector<int> _h,vector<int> l,vector<int> r){
	n=_h.size();
	q=l.size();
	h=_h;
	maxseg.init();
	
	ans.resize(q);
	for(int i=0;i<q;++i){
		int m=maxseg.qry(l[i],r[i]);
		qrys[m].pb({l[i],r[i],i});
	}
	
	llct=new lichao(0,n-1);
	rlct=new lichao(0,n-1);
	solve(0,n-1);
	
	return ans;
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 17916 KB Output is correct
2 Correct 17 ms 18700 KB Output is correct
3 Correct 14 ms 18772 KB Output is correct
4 Correct 14 ms 18732 KB Output is correct
5 Correct 13 ms 18772 KB Output is correct
6 Correct 14 ms 18964 KB Output is correct
7 Correct 13 ms 18800 KB Output is correct
8 Correct 13 ms 18988 KB Output is correct
9 Correct 15 ms 18800 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 17916 KB Output is correct
2 Correct 17 ms 18700 KB Output is correct
3 Correct 14 ms 18772 KB Output is correct
4 Correct 14 ms 18732 KB Output is correct
5 Correct 13 ms 18772 KB Output is correct
6 Correct 14 ms 18964 KB Output is correct
7 Correct 13 ms 18800 KB Output is correct
8 Correct 13 ms 18988 KB Output is correct
9 Correct 15 ms 18800 KB Output is correct
10 Correct 21 ms 19708 KB Output is correct
11 Correct 21 ms 19628 KB Output is correct
12 Correct 23 ms 19728 KB Output is correct
13 Correct 21 ms 19748 KB Output is correct
14 Correct 21 ms 19996 KB Output is correct
15 Correct 20 ms 19764 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 17876 KB Output is correct
2 Correct 59 ms 23788 KB Output is correct
3 Correct 311 ms 59656 KB Output is correct
4 Correct 281 ms 53060 KB Output is correct
5 Correct 253 ms 60716 KB Output is correct
6 Correct 262 ms 61308 KB Output is correct
7 Correct 335 ms 62692 KB Output is correct

Subtask #4
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 17876 KB Output is correct
2 Correct 59 ms 23788 KB Output is correct
3 Correct 311 ms 59656 KB Output is correct
4 Correct 281 ms 53060 KB Output is correct
5 Correct 253 ms 60716 KB Output is correct
6 Correct 262 ms 61308 KB Output is correct
7 Correct 335 ms 62692 KB Output is correct
8 Correct 266 ms 53696 KB Output is correct
9 Correct 247 ms 53280 KB Output is correct
10 Correct 247 ms 53612 KB Output is correct
11 Correct 266 ms 52988 KB Output is correct
12 Correct 238 ms 52676 KB Output is correct
13 Correct 233 ms 53240 KB Output is correct
14 Correct 275 ms 59600 KB Output is correct
15 Correct 295 ms 52652 KB Output is correct
16 Correct 306 ms 59740 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 17916 KB Output is correct
2 Correct 17 ms 18700 KB Output is correct
3 Correct 14 ms 18772 KB Output is correct
4 Correct 14 ms 18732 KB Output is correct
5 Correct 13 ms 18772 KB Output is correct
6 Correct 14 ms 18964 KB Output is correct
7 Correct 13 ms 18800 KB Output is correct
8 Correct 13 ms 18988 KB Output is correct
9 Correct 15 ms 18800 KB Output is correct
10 Correct 21 ms 19708 KB Output is correct
11 Correct 21 ms 19628 KB Output is correct
12 Correct 23 ms 19728 KB Output is correct
13 Correct 21 ms 19748 KB Output is correct
14 Correct 21 ms 19996 KB Output is correct
15 Correct 20 ms 19764 KB Output is correct
16 Correct 10 ms 17876 KB Output is correct
17 Correct 59 ms 23788 KB Output is correct
18 Correct 311 ms 59656 KB Output is correct
19 Correct 281 ms 53060 KB Output is correct
20 Correct 253 ms 60716 KB Output is correct
21 Correct 262 ms 61308 KB Output is correct
22 Correct 335 ms 62692 KB Output is correct
23 Correct 266 ms 53696 KB Output is correct
24 Correct 247 ms 53280 KB Output is correct
25 Correct 247 ms 53612 KB Output is correct
26 Correct 266 ms 52988 KB Output is correct
27 Correct 238 ms 52676 KB Output is correct
28 Correct 233 ms 53240 KB Output is correct
29 Correct 275 ms 59600 KB Output is correct
30 Correct 295 ms 52652 KB Output is correct
31 Correct 306 ms 59740 KB Output is correct
32 Correct 2775 ms 285896 KB Output is correct
33 Correct 1882 ms 285216 KB Output is correct
34 Correct 1962 ms 287864 KB Output is correct
35 Correct 2449 ms 288224 KB Output is correct
36 Correct 1850 ms 285528 KB Output is correct
37 Correct 1949 ms 288184 KB Output is correct
38 Correct 2500 ms 338436 KB Output is correct
39 Correct 2519 ms 338448 KB Output is correct
40 Correct 2432 ms 294272 KB Output is correct
41 Correct 2597 ms 383576 KB Output is correct
42 Correct 3032 ms 386092 KB Output is correct
43 Correct 3016 ms 385872 KB Output is correct
44 Correct 2836 ms 337860 KB Output is correct