oj.uz

답안 #433899

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
433899 2021-06-20T11:59:33 Z AugustinasJucas 모임들 (IOI18_meetings) C++14
17 / 100
 140 ms 11756 KB 
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
const int dydis = 2e5 + 10;
struct seg_tree{
	int l[dydis], r[dydis], val[dydis]; int dbInd = 0;
	int n;
	void build(int v = 1){
		if(v >= n){
			l[v] = r[v] = dbInd++;
		}else{
			build(v*2); build(v*2+1);
			l[v] = l[v*2]; r[v] = r[v*2+1];
		}
		val[v] = 0;
	}
	seg_tree(int dd){
		n = dd;
		build();
	}
	void change(int v, int L, int R, int x){
		if(L <= l[v] && r[v] <= R){
			val[v] = x;
		}else if(R < l[v] || r[v] < L){
			
		}else{
			change(v*2, L, R, x);
			change(v*2+1, L, R, x);
			val[v] = max(val[v*2], val[v*2+1]);
		}
	}
	int getMax(int v, int L, int R){
		if(L <= l[v] && r[v] <= R){
			return val[v];
		}else if(R < l[v] || r[v] < L){
			return 0;
		}else{
			return max(getMax(v*2, L, R), getMax(v*2+1, L, R));
		}
	}
};
vector<int> mas;
vector<pair<int, int> > vec;
vector<int> mxai;
int q;
int n;
vector<long long> mazas(){
	int pref[n][2], suf[n][2];
	for(auto &x : mas) x--;
	pref[0][0] = mas[0] == 0;
	pref[0][1] = mas[0] == 1;
	for(int i = 1; i < n; i++){
		pref[i][0] = pref[i-1][0] + (mas[i] == 0);
		pref[i][1] = pref[i-1][1] + (mas[i] == 1);
	}
	suf[n-1][0] = mas[n-1] == 0;
	suf[n-1][1] = mas[n-1] == 1;
	for(int i = n-2; i > -1; i--){
		suf[i][0] = suf[i+1][0] + (mas[i] == 0);
		suf[i][1] = suf[i+1][1] + (mas[i] == 1);
	}
	mxai.resize(n);
	for(int i = 0; i < n; i++){
		if(mas[i] == 1) continue;
		for(int j = i; j <= n; j++){
			if(j == n || mas[i] != mas[j]){
				for(int h = i; h < j; h++) mxai[h] = j - i;
				i = j - 1; break;
			}
		}
	}
	seg_tree medis(n);
	for(int i = 0; i < n; i++){
		medis.change(1, i, i, mxai[i]);
	}
	vector<long long> ret;
	for(auto x : vec){
		int L = x.first;
		int R = x.second;
		int mxas = 0;
		int LL = L, RR = R;
		//cout << "L = " << L << ", R = " << R << endl;
		if(mas[L] == 0){
			int l = L; int r = R; int mid;
			while(l <= r){
				mid = (l + r) / 2;
				//cout << "mid = " << mid << endl;
				if(pref[mid][1] == pref[L][1]){
					L = max(L, mid);
					l = mid+1;
				}else{
					r = mid-1;
				}
			}
			L++;
			if(L > R) {
				ret.push_back(RR - LL + 1);
				continue;
			}
		}
		if(mas[R] == 0){
			int l = L; int r = R; int mid;
			while(l <= r){
				mid = (l + r) / 2;
				if(suf[mid][1] == suf[R][1]){
					R = min(R, mid);
					r = mid-1;
				}else{
					l = mid+1;
				}
			}
			R--;
			if(L > R) {
				ret.push_back(RR - LL + 1);
				continue;
			}
		}
		mxas = max(RR-R, L-LL);
		//cout << "is [" << LL << "; "  << RR << "] i [" << L << "; " << R << "]\n";
		mxas = max(mxas, medis.getMax(1, L, R));
		ret.push_back((RR-LL + 1 - mxas) * 2 + mxas);
	}
	return ret;
	
}



vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
	q = L.size();
	n = H.size();
	mas = H; q = L.size();
	for(int i = 0; i < q; i++){
		vec.push_back({L[i], R[i]});
	}
	bool viendu = 1;
	for(auto x : mas) if(x > 2) viendu = 0;
	if(viendu){
		return mazas();
	}
	return {};
}

/*
10 1
1 1 1 1 2 1 1 2 1 1
0 0
*/

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 42 ms 4804 KB Output is correct
3 Correct 123 ms 11536 KB Output is correct
4 Correct 140 ms 11536 KB Output is correct
5 Correct 84 ms 11532 KB Output is correct
6 Correct 99 ms 11756 KB Output is correct
7 Correct 104 ms 11576 KB Output is correct

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 42 ms 4804 KB Output is correct
3 Correct 123 ms 11536 KB Output is correct
4 Correct 140 ms 11536 KB Output is correct
5 Correct 84 ms 11532 KB Output is correct
6 Correct 99 ms 11756 KB Output is correct
7 Correct 104 ms 11576 KB Output is correct
8 Incorrect 39 ms 6152 KB Unexpected end of file - int64 expected
9 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -