제출 #785894

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
785894		esomer	모임들 (IOI18_meetings)	C++17	36 / 100	445 ms	196432 KiB

meetings

#include<bits/stdc++.h>
#include "meetings.h"

using namespace std;

typedef long long ll;

const int K = 22;

vector<int> lw;

int get_mx(int l, int r, vector<vector<int>>& mx){
	int dist = r - l + 1;
	int k = lw[dist];
	return max(mx[k][r], mx[k][l + (1 << k) - 1]);
}

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
	int n = (int)H.size();
	int q = (int)L.size();
	if(n <= 5000 && q <= 5000){
		vector<vector<ll>> prefix(n, vector<ll>(n, 0));
		for(int i = 0; i < n; i++){
			vector<int> val(n, 0);
			int mx = 0;
			for(int j = i; j >= 0; j--){
				mx = max(mx, H[j]);
				val[j] = mx;
			}
			mx = 0;
			for(int j = i; j < n; j++){
				mx = max(mx, H[j]);
				val[j] = mx;
			}
			for(int j = 0; j < n; j++){
				if(j == 0) prefix[i][j] = val[j];
				else prefix[i][j] = prefix[i][j-1] + val[j];
			}
		}
		vector<ll> ans(q, 1e18);
		for(int k = 0; k < q; k++){
			int l = L[k];
			int r = R[k];
			for(int i = l; i <= r; i++){
				ll sum = prefix[i][r];
				if(l > 0) sum -= prefix[i][l-1];
				ans[k] = min(ans[k], sum);
			}
		}
		return ans;	
	}else{
		//H[i] <= 2.
		lw.resize(n+1);
		int pw = 0;
		int curr = 2;
		for(int i = 1; i <= n; i++){
			if(i == curr){pw++; curr *= 2;}
			lw[i] = pw;
		}
		set<int> two;
		for(int i = 0; i < n; i++){
			if(H[i] == 2) two.insert(i);
		}
		vector<int> val(n);
		for(int i = 0; i < n; i++){
			if(H[i] == 2){
				val[i] = 0;
				continue;
			}
			auto it = two.upper_bound(i);
			int l, r;
			if(it == two.end()){
				r = n;
			}else r = *it;
			if(it == two.begin()){
				l = -1;
			}else{
				it--;
				l = *it;
			}
			val[i] = r - l - 1;
		}
		vector<vector<int>> mx(K, vector<int>(n));
		for(int k = 0; k < K; k++){
			for(int i = 0; i < n; i++){
				if(k == 0) mx[k][i] = val[i];
				else{
					if(i - (1 << (k-1)) < 0) mx[k][i] = mx[k-1][i];
					else mx[k][i] = max(mx[k-1][i], mx[k-1][i - (1 << (k-1))]);
				}
			}
		}
		vector<ll> ans(q);
		for(int k = 0; k < q; k++){
			int l = L[k];
			int r = R[k];
			int _mx = 0;
			int first = -1;
			int second = r + 1;
			auto it = two.lower_bound(l);
			if(it != two.end() && *it <= r) first = *it;
			it = two.upper_bound(r);
			if(it != two.begin()){
				it--;
				if(*it >= l) second = *it;
			}
			if(first == -1) ans[k] = (r - l + 1);
			else{
				_mx = max(get_mx(first, second, mx), max(first - l, r - second));
				ans[k] = (r - l + 1) * 2 - _mx;
			}
		}
		return ans;
	}
}

//~ namespace {

//~ int read_int() {
  //~ int x;
  //~ if (scanf("%d", &x) != 1) {
    //~ fprintf(stderr, "Error while reading input\n");
    //~ exit(1);
  //~ }
  //~ return x;
//~ }

//~ }  // namespace

//~ int main() {
  //~ int N = read_int();
  //~ int Q = read_int();
  //~ std::vector<int> H(N);
  //~ for (int i = 0; i < N; ++i) {
    //~ H[i] = read_int();
  //~ }
  //~ std::vector<int> L(Q), R(Q);
  //~ for (int j = 0; j < Q; ++j) {
    //~ L[j] = read_int();
    //~ R[j] = read_int();
  //~ }

  //~ std::vector<long long> C = minimum_costs(H, L, R);
  //~ for (size_t j = 0; j < C.size(); ++j) {
    //~ printf("%lld\n", C[j]);
  //~ }
  //~ return 0;
//}

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40