oj.uz

답안 #97350

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
97350 2019-02-15T11:28:56 Z E869120 모임들 (IOI18_meetings) C++14
60 / 100
 5500 ms 117884 KB 
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

class RangeMinimumQuery {
	public:
	vector<long long> dat; int size_;
	
	void init(int sz) {
		size_ = 1;
		while (size_ < sz) size_ *= 2;
		dat.resize(size_ * 2, 0LL);
	}
	void update(int p, long long x) {
		p += size_; dat[p] = x;
		while (p >= 2) {
			p >>= 1;
			dat[p] = min(dat[p * 2], dat[p * 2 + 1]);
		}
	}
	long long query_(int l, int r, int a, int b, int u) {
		if (l <= a && b <= r) return dat[u];
		if (b <= l || r <= a) return 0LL;
		
		long long c1 = query_(l, r, a, (a + b) >> 1, u * 2);
		long long c2 = query_(l, r, (a + b) >> 1, b, u * 2 + 1);
		return min(c1, c2);
	}
	long long query(int l, int r) {
		return query_(l, r, 0, size_, 1);
	}
};

class RangeMaximumQuery {
	public:
	vector<long long> dat; int size_;
	
	void init(int sz) {
		size_ = 1;
		while (size_ < sz) size_ *= 2;
		dat.resize(size_ * 2, 0LL);
	}
	void update(int p, long long x) {
		p += size_; dat[p] = x;
		while (p >= 2) {
			p >>= 1;
			dat[p] = max(dat[p * 2], dat[p * 2 + 1]);
		}
	}
	long long query_(int l, int r, int a, int b, int u) {
		if (l <= a && b <= r) return dat[u];
		if (b <= l || r <= a) return 0LL;
		
		long long c1 = query_(l, r, a, (a + b) >> 1, u * 2);
		long long c2 = query_(l, r, (a + b) >> 1, b, u * 2 + 1);
		return max(c1, c2);
	}
	long long query(int l, int r) {
		return query_(l, r, 0, size_, 1);
	}
};

long long N, Q, H[750009], T[750009], sm[750009]; pair<int, int> dp[5009][5009];

void dfs(int cl, int cr) {
	if (cl > cr) return;
	int cm = dp[cl][cr].second; long long cost = dp[cl][cr].first;
	//cout << "cl = " << cl << ", cr = " << cr << ", cm = " << cm << ", cost = " << cost << endl;
	T[cl] += cost * (cr - cm + 1);
	T[cm] += cost * (cm - cl);
	T[cm + 1] -= cost * (cr - cm);
	T[cr + 1] -= cost * (cm - cl + 1);
	dfs(cl, cm - 1);
	dfs(cm + 1, cr);
}

long long ranged(long long cl, long long cr) {
	return sm[cr] - sm[cl];
}

vector<long long> minimum_costs(vector<int> HH, vector<int> L, vector<int> R) {
	int maxh = 0; for (int i = 0; i < HH.size(); i++) maxh = max(maxh, HH[i]);
	
	if(maxh <= 20) {
		// -------------------------------------- Initialize / Precalc Phase -------------------------
		N = HH.size(); Q = L.size();
		for (int i = 0; i < N; i++) H[i] = HH[i];
		for (int i = 0; i < N; i++) sm[i + 1] = sm[i] + H[i];
		
		vector<long long> DD[21];
		for (int i = 0; i < 21; i++) DD[i].clear();
		for (int i = 0; i < N; i++) {
			for (int j = 1; j <= H[i]; j++) DD[j].push_back(i);
		}
		
		RangeMaximumQuery Z[21], ZZ; ZZ.init(N + 2);
		for (int i = 0; i < N; i++) ZZ.update(i, H[i]);
		
		for (int i = 0; i < 21; i++) Z[i].init(N + 2);
		for (int i = 0; i < N; i++) {
			for (int j = 1; j <= H[i]; j++) Z[j].update(i, 0);
			
			long long sss = 0;
			for (int j = H[i] + 1; j <= 20; j++) {
				int pos1 = lower_bound(DD[j].begin(), DD[j].end(), i) - DD[j].begin();
				int pl = -1, pr = N;
				if (DD[j].size() >= 1){
					if (pos1 >= 1) pl = DD[j][pos1 - 1]; if (pos1 < DD[j].size()) pr = DD[j][pos1];
				}
				sss += (pr - pl - 1); //cout << i << " : " << j << ", " << sss << endl;
				Z[j].update(i, sss);
			}
		}
		
		// ------------------------------ Final Query Calculation Part ----------------------------
		
		vector<long long> ans;
		for (int t = 0; t < Q; t++) {
			long long LL[22], RR[22], maxp = ZZ.query(L[t], R[t] + 1);
			
			for (int i = 1; i <= maxp; i++) {
				int pos1 = lower_bound(DD[i].begin(), DD[i].end(), L[t]) - DD[i].begin();
				LL[i] = DD[i][pos1];
			}
			for (int i = 1; i <= maxp; i++) {
				int pos1 = lower_bound(DD[i].begin(), DD[i].end(), R[t] + 1) - DD[i].begin(); pos1--;
				RR[i] = DD[i][pos1];
			}
			LL[maxp + 1] = R[t] + 1; RR[maxp + 1] = L[t] - 1;
			
			// Leftmost Part
			long long minx = (1LL << 60);
			for (int i = 1; i <= maxp - 1; i++) {
				long long Z1 = Z[i].query(LL[i], LL[i + 1]);
				long long Z2 = 0; for (int j = i + 1; j <= maxp; j++) Z2 += 1LL * j * (LL[j + 1] - LL[j]);
				long long Z3 = 1LL * i * (LL[i + 1] - L[t]) - Z1;
				minx = min(minx, Z2 + Z3); //cout << i << " " << LL[i] << " " << LL[i + 1] << " " << Z1 << " " << Z2 << " " << Z3 << endl;
			}
			for (int i = 1; i <= maxp - 1; i++) {
				long long Z1 = Z[i].query(RR[i + 1] + 1, RR[i] + 1);
				long long Z2 = 0; for (int j = i + 1; j <= maxp; j++) Z2 += 1LL * j * (RR[j] - RR[j + 1]);
				long long Z3 = 1LL * i * (R[t] - RR[i + 1]) - Z1;
				minx = min(minx, Z2 + Z3);
			}
			long long Z1 = Z[maxp].query(LL[maxp], RR[maxp] + 1);
			long long Z2 = 1LL * maxp * (R[t] - L[t] + 1) - Z1;
			minx = min(minx, Z2);
			ans.push_back(minx);
		}
		return ans;
	}
	else{
		N = HH.size(); Q = L.size();
		for (int i = 0; i < N; i++) H[i] = HH[i];
		
		for (int i = 0; i < N; i++) {
			pair<int, int> BASE = make_pair(-1, -1);
			for (int j = i; j < N; j++) {
				BASE = max(BASE, make_pair((int)H[j], j));
				dp[i][j] = BASE;
			}
		}
		
		vector<long long> ans;
		for (int i = 0; i < Q; i++) {
			for (int j = 0; j <= N; j++) T[j] = 0;
			dfs(L[i], R[i]);
			for (int j = 1; j <= N; j++) T[j] += T[j - 1];
			
			long long rem = (1LL << 60);
			for (int j = L[i]; j <= R[i]; j++) rem = min(rem, T[j]);
			ans.push_back(rem);
		}
		return ans;
	}
}

Compilation message

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:82:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  int maxh = 0; for (int i = 0; i < HH.size(); i++) maxh = max(maxh, HH[i]);
                                ~~^~~~~~~~~~~
meetings.cpp:108:6: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
      if (pos1 >= 1) pl = DD[j][pos1 - 1]; if (pos1 < DD[j].size()) pr = DD[j][pos1];
      ^~
meetings.cpp:108:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
      if (pos1 >= 1) pl = DD[j][pos1 - 1]; if (pos1 < DD[j].size()) pr = DD[j][pos1];
                                           ^~
meetings.cpp:108:52: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if (pos1 >= 1) pl = DD[j][pos1 - 1]; if (pos1 < DD[j].size()) pr = DD[j][pos1];
                                               ~~~~~^~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 51 ms 47776 KB Output is correct
3 Correct 51 ms 47780 KB Output is correct
4 Correct 51 ms 47772 KB Output is correct
5 Correct 52 ms 47864 KB Output is correct
6 Correct 47 ms 47804 KB Output is correct
7 Correct 51 ms 47736 KB Output is correct
8 Correct 49 ms 47736 KB Output is correct
9 Correct 50 ms 47836 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 51 ms 47776 KB Output is correct
3 Correct 51 ms 47780 KB Output is correct
4 Correct 51 ms 47772 KB Output is correct
5 Correct 52 ms 47864 KB Output is correct
6 Correct 47 ms 47804 KB Output is correct
7 Correct 51 ms 47736 KB Output is correct
8 Correct 49 ms 47736 KB Output is correct
9 Correct 50 ms 47836 KB Output is correct
10 Correct 467 ms 117760 KB Output is correct
11 Correct 1152 ms 117748 KB Output is correct
12 Correct 474 ms 117724 KB Output is correct
13 Correct 1221 ms 117732 KB Output is correct
14 Correct 445 ms 117884 KB Output is correct
15 Correct 447 ms 117752 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 100 ms 4908 KB Output is correct
3 Correct 445 ms 52268 KB Output is correct
4 Correct 432 ms 51812 KB Output is correct
5 Correct 337 ms 52212 KB Output is correct
6 Correct 400 ms 52204 KB Output is correct
7 Correct 400 ms 52264 KB Output is correct

Subtask #4
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 100 ms 4908 KB Output is correct
3 Correct 445 ms 52268 KB Output is correct
4 Correct 432 ms 51812 KB Output is correct
5 Correct 337 ms 52212 KB Output is correct
6 Correct 400 ms 52204 KB Output is correct
7 Correct 400 ms 52264 KB Output is correct
8 Correct 1792 ms 60436 KB Output is correct
9 Correct 1113 ms 60128 KB Output is correct
10 Correct 1761 ms 60392 KB Output is correct
11 Correct 1792 ms 59768 KB Output is correct
12 Correct 1144 ms 59936 KB Output is correct
13 Correct 1768 ms 59936 KB Output is correct
14 Correct 1821 ms 63260 KB Output is correct
15 Correct 1258 ms 53688 KB Output is correct
16 Correct 1461 ms 59920 KB Output is correct

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 51 ms 47776 KB Output is correct
3 Correct 51 ms 47780 KB Output is correct
4 Correct 51 ms 47772 KB Output is correct
5 Correct 52 ms 47864 KB Output is correct
6 Correct 47 ms 47804 KB Output is correct
7 Correct 51 ms 47736 KB Output is correct
8 Correct 49 ms 47736 KB Output is correct
9 Correct 50 ms 47836 KB Output is correct
10 Correct 467 ms 117760 KB Output is correct
11 Correct 1152 ms 117748 KB Output is correct
12 Correct 474 ms 117724 KB Output is correct
13 Correct 1221 ms 117732 KB Output is correct
14 Correct 445 ms 117884 KB Output is correct
15 Correct 447 ms 117752 KB Output is correct
16 Correct 2 ms 380 KB Output is correct
17 Correct 100 ms 4908 KB Output is correct
18 Correct 445 ms 52268 KB Output is correct
19 Correct 432 ms 51812 KB Output is correct
20 Correct 337 ms 52212 KB Output is correct
21 Correct 400 ms 52204 KB Output is correct
22 Correct 400 ms 52264 KB Output is correct
23 Correct 1792 ms 60436 KB Output is correct
24 Correct 1113 ms 60128 KB Output is correct
25 Correct 1761 ms 60392 KB Output is correct
26 Correct 1792 ms 59768 KB Output is correct
27 Correct 1144 ms 59936 KB Output is correct
28 Correct 1768 ms 59936 KB Output is correct
29 Correct 1821 ms 63260 KB Output is correct
30 Correct 1258 ms 53688 KB Output is correct
31 Correct 1461 ms 59920 KB Output is correct
32 Execution timed out 5536 ms 115908 KB Time limit exceeded
33 Halted 0 ms 0 KB -