oj.uz

답안 #738587

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
738587 2023-05-09T06:37:34 Z huajun 모임들 (IOI18_meetings) C++14
100 / 100
 3692 ms 494408 KB 
#include "meetings.h"
#include<bitset>
#include<compare>
#include<functional>
#include<tuple>
#include<utility>
#include<cstring>
#include<string>
#include<deque>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<vector>
#include<iterator>
#include<ranges>
#include<algorithm>
#include<random>
#include<fstream>
#include<iostream>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long int ll;
typedef long double ld;
#define mp make_pair
#define pb push_back
#define eb emplace_back
vector<pair<ll,ll> > dq, pa;
ll aj[750005][2], l[750005], r[750005], root, h[750005], ans[750005];
struct node{
	ll s, e, m, lazy, vm, vc;
	node *l, *r;
	node(ll _s, ll _e): s(_s), e(_e), m((_s+_e)/2), lazy(0), vm(0), vc(1e17){
		if(s!=e){
			l = new node(s,m);
			r = new node(m+1, e);
		}
	}
	void propo(){
		if(lazy){
			l->vc += lazy;
			r->vc += lazy;
			l->lazy += lazy;
			r->lazy += lazy;
			lazy = 0;
		}
	}
	void update(ll x,ll y, ll nm, ll nc){
		if(s==x&&y==e){
			if((vm|vc)==0){
				vm = nm;
				vc = nc;
				return;
			}
			if(nm*m+nc < vm*m+vc){
				swap(nm, vm);
				swap(vc, nc);
			}
			if(s!=e){
				propo();
				if(vm > nm)r->update(m+1, e, nm, nc);
				if(vm < nm)l->update(s, m, nm, nc);
			}
			return;
		}
		propo();
		if(y<=m)l->update(x, y, nm, nc);
		else if(x>m)r->update(x, y, nm, nc);
		else{
			l->update(x, m, nm, nc);
			r->update(m+1, y, nm, nc);
		}
	}
	void add(ll x,ll y, ll v){
		if(s==x&&e==y){
			lazy+=v;
			vc+=v;
			return;
		}
		propo();
		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 query(ll x){
		ll a = 1e17;
		if(vm | vc){
			a = vm*x+vc;
		}
		if(s==e)return a;
		propo();
		if(x<=m)return min(a, l->query(x));
		else return min(a, r->query(x));
	}
} *rootS, *rootP;
vector<tuple<ll,ll, ll> > v, qn[750005];
vector<pair<ll,ll> > dq2;
void dfs(ll x){
	ll a = 0, b = 0;
	if(~aj[x][0]){
		dfs(aj[x][0]);
		a = rootP->query(x-1);
	}
	if(~aj[x][1]){
		dfs(aj[x][1]);
		b = rootS->query(x+1);
	}
	//cout<<x<<" "<<l[x]<<" "<<r[x]<<" "<<a<<" "<<b<<" val"<<endl;
	for(auto [ql, qr, q]:qn[x]){
	//	cout<<ql<<" "<<qr<<" "<<q<<endl;
	//	cout<<((qr>x)?rootP->query(qr):0)<<" "<<((ql<x)? rootS->query(ql):0)<<" "<<h[x]<<endl;
		ans[q] = min(((qr>x)?rootP->query(qr):0) + (x-ql+1)*h[x],((ql<x)? rootS->query(ql):0)+(qr-x+1)*h[x]);
	}
//	cout<<x<<" "<<l[x]<<" "<<r[x]<<" "<<a<<" "<<b<<" dfs"<<endl;
	rootS->update(x, x, 0, 0);
	rootP->update(x, x, 0, 0);
	rootS->add(l[x], x, (r[x] - x+1)*h[x]);
	if(x>l[x])rootS->add(x, x, (x-l[x])*h[x]);
	rootP->add(x, r[x], (x - l[x]+1)*h[x]);
	if(r[x]>x)rootP->add(x, x, (r[x] - x)*h[x]);
	rootS->update(l[x], x, -h[x], b+(x+1)*h[x]);
	rootP->update(x, r[x], h[x], a+(1-x)*h[x]);
	//cout<<x<<" "<<l[x]<<" "<<r[x]<<" "<<rootP->query(r[x])<<" "<<rootS->query(l[x])<<" dfs"<<endl;
//	for(ll i=0;i<5;i++)cout<<rootP->query(i)<<" ";cout<<"\n";
//	for(ll i=0;i<5;i++)cout<<rootS->query(i)<<" ";cout<<"\n";
}
vector<long long> minimum_costs(vector<int> H, vector<int> L,
                                     vector<int> R) {
  int Q = L.size();
  vector<long long> C(Q);
  int n = H.size();
  ll i,j,k,a,b,c,x,y,z;
  memset(aj, -1, sizeof(aj));
  for(i=0;i<Q;i++){
	v.eb(R[i], L[i], i);
  }
  sort(all(v));
  ll cur = 0;
  for(i=0;i<n;i++){
	  h[i] = H[i];
	pa.eb(2e9, -1);
	auto it = mp((ll)H[i], i);
	while(dq.size()&&dq.back() <= it)dq.pop_back();
	if(dq.size()){
		pa[i] = dq.back();
		l[i] = dq.back().second+1;
	}else l[i] = 0;
	dq.pb(it);
	
	while(dq2.size()&&dq2.back().second<=h[i])dq2.pop_back();
	dq2.pb(mp(i, h[i]));
	while(cur<Q&&get<0>(v[cur])==i){
		a = lower_bound(dq2.begin(), dq2.end(), mp(get<1>(v[cur]), -1ll)) - dq2.begin();
		qn[dq2[a].first].eb(get<1>(v[cur]), get<0>(v[cur]), get<2>(v[cur]));
		cur++;
	}
  }
  dq.clear();
  for(i=n-1;i>=0;i--){
	auto it = mp((ll)H[i], i);
	while(dq.size()&&dq.back() <= it)dq.pop_back();
	if(dq.size()){
		pa[i] = min(dq.back(), pa[i]);
		r[i] = dq.back().second-1;
	}else r[i] = n-1;
	dq.pb(it);
  }
  for(i=0;i<n;i++){
	if(pa[i].second==-1)root = i;
	else{
		aj[pa[i].second][pa[i].second < i] = i;
	}
  }
  rootP = new node(0, n-1);
  rootS = new node(0, n-1);
  dfs(root);
  for(i=0;i<Q;i++)C[i] = ans[i];
  return C;
}

Compilation message

meetings.cpp: In function 'void dfs(ll)':
meetings.cpp:117:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  117 |  for(auto [ql, qr, q]:qn[x]){
      |           ^
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:140:8: warning: unused variable 'j' [-Wunused-variable]
  140 |   ll i,j,k,a,b,c,x,y,z;
      |        ^
meetings.cpp:140:10: warning: unused variable 'k' [-Wunused-variable]
  140 |   ll i,j,k,a,b,c,x,y,z;
      |          ^
meetings.cpp:140:14: warning: unused variable 'b' [-Wunused-variable]
  140 |   ll i,j,k,a,b,c,x,y,z;
      |              ^
meetings.cpp:140:16: warning: unused variable 'c' [-Wunused-variable]
  140 |   ll i,j,k,a,b,c,x,y,z;
      |                ^
meetings.cpp:140:18: warning: unused variable 'x' [-Wunused-variable]
  140 |   ll i,j,k,a,b,c,x,y,z;
      |                  ^
meetings.cpp:140:20: warning: unused variable 'y' [-Wunused-variable]
  140 |   ll i,j,k,a,b,c,x,y,z;
      |                    ^
meetings.cpp:140:22: warning: unused variable 'z' [-Wunused-variable]
  140 |   ll i,j,k,a,b,c,x,y,z;
      |                      ^

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 29652 KB Output is correct
2 Correct 17 ms 30776 KB Output is correct
3 Correct 19 ms 30676 KB Output is correct
4 Correct 18 ms 30760 KB Output is correct
5 Correct 18 ms 30804 KB Output is correct
6 Correct 18 ms 31020 KB Output is correct
7 Correct 18 ms 30676 KB Output is correct
8 Correct 18 ms 31024 KB Output is correct
9 Correct 19 ms 30984 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 29652 KB Output is correct
2 Correct 17 ms 30776 KB Output is correct
3 Correct 19 ms 30676 KB Output is correct
4 Correct 18 ms 30760 KB Output is correct
5 Correct 18 ms 30804 KB Output is correct
6 Correct 18 ms 31020 KB Output is correct
7 Correct 18 ms 30676 KB Output is correct
8 Correct 18 ms 31024 KB Output is correct
9 Correct 19 ms 30984 KB Output is correct
10 Correct 28 ms 32012 KB Output is correct
11 Correct 22 ms 31968 KB Output is correct
12 Correct 24 ms 32100 KB Output is correct
13 Correct 23 ms 32024 KB Output is correct
14 Correct 24 ms 32404 KB Output is correct
15 Correct 22 ms 32072 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 29652 KB Output is correct
2 Correct 58 ms 37580 KB Output is correct
3 Correct 225 ms 83480 KB Output is correct
4 Correct 236 ms 76396 KB Output is correct
5 Correct 180 ms 83308 KB Output is correct
6 Correct 184 ms 84284 KB Output is correct
7 Correct 207 ms 86792 KB Output is correct

Subtask #4
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 29652 KB Output is correct
2 Correct 58 ms 37580 KB Output is correct
3 Correct 225 ms 83480 KB Output is correct
4 Correct 236 ms 76396 KB Output is correct
5 Correct 180 ms 83308 KB Output is correct
6 Correct 184 ms 84284 KB Output is correct
7 Correct 207 ms 86792 KB Output is correct
8 Correct 218 ms 77292 KB Output is correct
9 Correct 176 ms 76940 KB Output is correct
10 Correct 186 ms 77296 KB Output is correct
11 Correct 216 ms 76472 KB Output is correct
12 Correct 180 ms 75648 KB Output is correct
13 Correct 183 ms 76800 KB Output is correct
14 Correct 221 ms 83516 KB Output is correct
15 Correct 213 ms 75952 KB Output is correct
16 Correct 248 ms 83720 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 29652 KB Output is correct
2 Correct 17 ms 30776 KB Output is correct
3 Correct 19 ms 30676 KB Output is correct
4 Correct 18 ms 30760 KB Output is correct
5 Correct 18 ms 30804 KB Output is correct
6 Correct 18 ms 31020 KB Output is correct
7 Correct 18 ms 30676 KB Output is correct
8 Correct 18 ms 31024 KB Output is correct
9 Correct 19 ms 30984 KB Output is correct
10 Correct 28 ms 32012 KB Output is correct
11 Correct 22 ms 31968 KB Output is correct
12 Correct 24 ms 32100 KB Output is correct
13 Correct 23 ms 32024 KB Output is correct
14 Correct 24 ms 32404 KB Output is correct
15 Correct 22 ms 32072 KB Output is correct
16 Correct 15 ms 29652 KB Output is correct
17 Correct 58 ms 37580 KB Output is correct
18 Correct 225 ms 83480 KB Output is correct
19 Correct 236 ms 76396 KB Output is correct
20 Correct 180 ms 83308 KB Output is correct
21 Correct 184 ms 84284 KB Output is correct
22 Correct 207 ms 86792 KB Output is correct
23 Correct 218 ms 77292 KB Output is correct
24 Correct 176 ms 76940 KB Output is correct
25 Correct 186 ms 77296 KB Output is correct
26 Correct 216 ms 76472 KB Output is correct
27 Correct 180 ms 75648 KB Output is correct
28 Correct 183 ms 76800 KB Output is correct
29 Correct 221 ms 83516 KB Output is correct
30 Correct 213 ms 75952 KB Output is correct
31 Correct 248 ms 83720 KB Output is correct
32 Correct 1736 ms 383308 KB Output is correct
33 Correct 1377 ms 380384 KB Output is correct
34 Correct 1360 ms 386896 KB Output is correct
35 Correct 1841 ms 386404 KB Output is correct
36 Correct 1322 ms 383236 KB Output is correct
37 Correct 1426 ms 387344 KB Output is correct
38 Correct 1887 ms 440368 KB Output is correct
39 Correct 1909 ms 440332 KB Output is correct
40 Correct 2048 ms 394456 KB Output is correct
41 Correct 3165 ms 490036 KB Output is correct
42 Correct 3692 ms 494408 KB Output is correct
43 Correct 3611 ms 494348 KB Output is correct
44 Correct 3008 ms 440892 KB Output is correct