oj.uz

답안 #596307

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
596307 2022-07-14T15:01:46 Z FatihSolak 모임들 (IOI18_meetings) C++17
41 / 100
 3972 ms 16708 KB 
#include "meetings.h"
#include <bits/stdc++.h>
#define N 100005
using namespace std;
struct SegTree{
	vector<long long> t,lazy;
	int n;
	SegTree(int size){
		n = size;
		t.assign(4*n,0);
		lazy.assign(4*n,0);
	}
	void push(int v){
		t[v*2] += lazy[v];
		t[v*2+1] += lazy[v];
		lazy[v*2] += lazy[v];
		lazy[v*2+1] += lazy[v];
		lazy[v] = 0;
	}
	void upd(int v,int tl,int tr,int l,int r,long long val){
		if(tr < l || r < tl){
			return;
		}
		if(l <= tl && tr <= r){
			t[v] += val;
			lazy[v] += val;
			return;
		}
		push(v);
		int tm = (tl + tr)/2;
		upd(v*2,tl,tm,l,r,val);
		upd(v*2+1,tm+1,tr,l,r,val);
		t[v] = min(t[v*2],t[v*2+1]);
	}
	long long get(int v,int tl,int tr,int l,int r){
		if(tr < l || r < tl){
			return 1e18;
		}
		if(l <= tl && tr <= r){
			return t[v];
		}
		push(v);
		int tm = (tl + tr)/2;
		return min(get(v*2,tl,tm,l,r),get(v*2+1,tm+1,tr,l,r));
	}
	void upd(int l,int r,long long val){
		upd(1,0,n-1,l,r,val);
	}
	long long get(int l,int r){
		return get(1,0,n-1,l,r);
	}
};
int lval[N][2];
int rval[N][2];
vector<int> pos[N];
vector<long long> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
	int q = l.size();
	int n = h.size();
	SegTree t(n);
	int maxi = 0;
	for(int i = 0;i<n;i++){
		maxi = max(maxi,h[i]);
		t.upd(i,i,-h[i]);
	}
	vector<int> st0,st1;
	for(int i = 0;i<n;i++){
		while(st0.size() && h[st0.back()] <= h[i])
			st0.pop_back();
		while(st1.size() && h[st1.back()] < h[i])
			st1.pop_back();
		lval[i][0] = lval[i][1] = -1;
		if(st0.size()){
			lval[i][0] = st0.back();
		}
		if(st1.size()){
			lval[i][1] = st1.back();
		}
		st0.push_back(i);
		st1.push_back(i);
	}
	st0.clear(),st1.clear();
	for(int i = n-1;i>=0;i--){
		while(st0.size() && h[st0.back()] <= h[i])
			st0.pop_back();
		while(st1.size() && h[st1.back()] < h[i])
			st1.pop_back();
		rval[i][0] = rval[i][1] = n;
		if(st0.size()){
			rval[i][0] = st0.back();
		}
		if(st1.size()){
			rval[i][1] = st1.back();
		}
		st0.push_back(i);
		st1.push_back(i);
	}
	//cout << endl;
	for(int i = 0;i<n;i++){
		//cout << i << " " << rval[i][1] << " " << lval[i][0] << endl;
		t.upd(i,rval[i][1] - 1,(long long)h[i] * (i - lval[i][0]));
		t.upd(lval[i][1] + 1,i,(long long)h[i] * (rval[i][0] - i));
	}

	for(int i = 0;i<n;i++){
		pos[h[i]].push_back(i);
	}
	for(int i = 1;i<=maxi;i++){
		pos[i].push_back(n);
	}
	// for(int i = 0;i<n;i++){
	// 	cout << t.get(i,i) << " ";
	// }
	// cout << endl;
	vector<long long> res(q);
	for(int i = 0;i<q;i++){
		vector<pair<pair<int,int>,long long>> changes;
		for(int j = 1;j<=maxi;j++){
			int lpos,rpos;
			if(pos[j][0] < l[i]){
				lpos = prev(lower_bound(pos[j].begin(),pos[j].end(),l[i])) - pos[j].begin();
				long long val = (long long)(pos[j][lpos] - lval[pos[j][lpos]][0]) * j;
				changes.push_back({ {pos[j][lpos], rval[pos[j][lpos]][1]-1}   ,-val});
			}
			if(pos[j].size() > 1 && pos[j][pos[j].size() - 2] > r[i]){
				rpos = upper_bound(pos[j].begin(),pos[j].end(),r[i]) - pos[j].begin();
				long long val = (long long)(rval[pos[j][rpos]][0] - pos[j][rpos]) * j;
				changes.push_back({ { lval[pos[j][rpos]][1]+1,pos[j][rpos]}   ,-val});
			}
			if(*lower_bound(pos[j].begin(),pos[j].end(),l[i]) > r[i])continue;
			lpos = lower_bound(pos[j].begin(),pos[j].end(),l[i]) - pos[j].begin();
			rpos = prev(upper_bound(pos[j].begin(),pos[j].end(),r[i])) - pos[j].begin();
			if(lval[pos[j][lpos]][0] + 1 < l[i]){
				long long val = (long long)(l[i] - lval[pos[j][lpos]][0] - 1) * j;
				int ll = lpos,rr = rpos;
				while(ll < rr){
					int m = (ll + rr + 1)/2;
					if(lval[pos[j][m]][0] < l[i]){
						ll = m;
					}
					else rr = m-1;
				}
				changes.push_back({ {pos[j][lpos], rval[pos[j][ll]][1]-1}   ,-val});
			}
			if(rval[pos[j][rpos]][0] - 1 > r[i]){
				long long val = (long long)(rval[pos[j][rpos]][0] - r[i] - 1) * j;
				int ll = lpos,rr = rpos;
				while(ll < rr){
					int m = (ll + rr)/2;
					if(rval[pos[j][m]][0] > r[i]){
						rr = m;
					}
					else ll = m+1;
				}
				changes.push_back({ { lval[pos[j][ll]][1]+1,pos[j][rpos]}   ,-val});
			}

		}
		for(auto u:changes){
			t.upd(u.first.first,u.first.second,u.second);
		}
		// for(int i = 0;i<n;i++){
		// 	cout << t.get(i,i) << " ";
		// }
		// cout << endl;
		res[i] = t.get(l[i],r[i]);
		for(auto u:changes){
			t.upd(u.first.first,u.first.second,-u.second);
		}
	}
	return res;
}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 5204 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 5204 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 247 ms 4576 KB Output is correct
3 Correct 759 ms 16224 KB Output is correct
4 Correct 978 ms 16144 KB Output is correct
5 Correct 498 ms 16464 KB Output is correct
6 Correct 713 ms 16448 KB Output is correct
7 Correct 735 ms 16708 KB Output is correct

Subtask #4
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 247 ms 4576 KB Output is correct
3 Correct 759 ms 16224 KB Output is correct
4 Correct 978 ms 16144 KB Output is correct
5 Correct 498 ms 16464 KB Output is correct
6 Correct 713 ms 16448 KB Output is correct
7 Correct 735 ms 16708 KB Output is correct
8 Correct 3441 ms 16352 KB Output is correct
9 Correct 2522 ms 16348 KB Output is correct
10 Correct 3447 ms 16308 KB Output is correct
11 Correct 3662 ms 16276 KB Output is correct
12 Correct 2619 ms 16280 KB Output is correct
13 Correct 3402 ms 16224 KB Output is correct
14 Correct 3039 ms 16380 KB Output is correct
15 Correct 3972 ms 16052 KB Output is correct
16 Correct 3343 ms 16468 KB Output is correct

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 5204 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -