oj.uz

Submission #122092

# Submission time Handle Problem Language Result Execution time Memory
122092 2019-06-27T14:33:43 Z SirCeness Meetings (IOI18_meetings) C++14
17 / 100
 241 ms 6988 KB 
#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;

int n, q;
vector<int> arr;
int st[400005][3];

void stc(int node, int l, int r){
	if (l == r) st[node][0] = st[node][1] = st[node][2] = (arr[l] == 1);
	else {
		int m = (l+r)/2;
		stc(node*2, l, m);
		stc(node*2+1, m+1, r);
		
		st[node][0] = max(max(st[node*2][0], st[node*2+1][0]), st[node*2][2] + st[node*2+1][1]);
		
		if (st[node*2][1] == (m-l+1)) st[node][1] = (m-l+1) + st[node*2+1][1];
		else st[node][1] = st[node*2][1];
		
		if (st[node*2+1][2] == (r-m)) st[node][2] = st[node*2][2] + (r-m);
		else st[node][2] = st[node*2+1][2];
	}
}

int stq(int node, int l, int r, int sl, int sr, int mode){
	//cout << "stq(" << l << ", " << r << ", " << sl << ", " << sr << ", " << mode << ")" << endl;
	if (sl <= l && r <= sr){
		return st[node][mode];
	} else if (r < sl || sr < l){
		return 0;
	} else {
		int m = (l+r)/2;
		
		if (mode == 0){
			int ans1 = stq(node*2, l, m, sl, sr, 0);
			int ans2 = stq(node*2+1, m+1, r, sl, sr, 0);
			int ans3 = stq(node*2, l, m, sl, sr, 2) + stq(node*2+1, m+1, r, sl, sr, 1);
			return max(max(ans1, ans2), ans3);
		} else if (mode == 1){
			int ans1 = 0, ans2 = 0;
			ans1 = stq(node*2, l, m, sl, sr, 1);
			if (ans1 == (m-(max(sl, l))+1)) ans2 = ans1 + stq(node*2+1, m+1, r, sl, sr, 1);
			return max(ans1, ans2);
		} else if (mode == 2){
			int ans1 = 0, ans2 = 0;
			ans1 = stq(node*2+1, m+1, r, sl, sr, 2);
			if (ans1 == min(sr, r)-m) ans2 = ans1 + stq(node*2, l, m, sl, sr, 2);
			return max(ans1, ans2);
		} else assert(0);
	}
}

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
	n = H.size();
	q = L.size();
	arr = H;
	vector<ll> ans(q);
	stc(1, 0, n-1);
	for (int i = 0; i < q; i++){
		ans[i] = (R[i]-L[i]+1)*2-stq(1, 0, n-1, L[i], R[i], 0);
		//ans[i] = stq(1, 0, n-1, L[i], R[i], 0);
	}
	return ans;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 63 ms 1884 KB Output is correct
3 Correct 179 ms 6988 KB Output is correct
4 Correct 216 ms 6904 KB Output is correct
5 Correct 127 ms 6936 KB Output is correct
6 Correct 187 ms 6936 KB Output is correct
7 Correct 241 ms 6876 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 63 ms 1884 KB Output is correct
3 Correct 179 ms 6988 KB Output is correct
4 Correct 216 ms 6904 KB Output is correct
5 Correct 127 ms 6936 KB Output is correct
6 Correct 187 ms 6936 KB Output is correct
7 Correct 241 ms 6876 KB Output is correct
8 Incorrect 183 ms 6940 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 328 KB Output isn't correct
2 Halted 0 ms 0 KB -