oj.uz

Submission #246798

# Submission time Handle Problem Language Result Execution time Memory
246798 2020-07-10T09:38:50 Z srvlt Meetings (IOI18_meetings) C++14
36 / 100
 844 ms 301604 KB 
#include "meetings.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
template <typename T> using ord_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int n = 5003, n2 = 1e5 + 123;
int mx[n][n], h[n2];
ll p[n][n], s[n][n];

struct Node {
	int l = 0, r = 0;
	int ans = 0, P = 0, S = 0;
	void clean() {
		l = r = ans = P = S = 0;
	}
};

Node merge(Node a, Node b) {
	if (a.l == 0 && a.r == 0) return b;
	Node c;
	c.l = a.l, c.r = b.r;
	c.P = a.P;
	if (a.P == a.r - a.l + 1)
		c.P += b.P;
	c.S = b.S;
	if (b.S == b.r - b.l + 1)
		c.S += a.S;
	c.ans = max({a.ans, b.ans, a.S + b.P});
	return c;
}
Node t[(1 << 18) + 1];

void build(int v, int l, int r) {
	t[v].l = l, t[v].r = r;
	if (l == r) {
		t[v].P = t[v].S = t[v].ans = (h[l - 1] == 1);
		return;
	}
	int m = l + r >> 1;
	build(v << 1, l, m);
	build(v << 1 | 1, m + 1, r);
	t[v] = merge(t[v << 1], t[v << 1 | 1]);
}
Node tmp;

void get(int v, int l, int r) {
	if (t[v].l > r || t[v].r < l) return;
	if (t[v].l >= l && t[v].r <= r) {
		tmp = merge(tmp, t[v]);
		return;
	}
	get(v << 1, l, r);
	get(v << 1 | 1, l, r);
}

int getans(int l, int r) {
	tmp.clean();
	get(1, l, r);
	return tmp.ans;
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
  int Q = L.size();
  std::vector<long long> C(Q);
  int N = SZ(H);
  for (int i = 0; i < N; i++) h[i] = H[i];
  
  if (N <= 5000 && Q <= 5000) {
	for (int i = 0; i < N; i++)
		for (int j = i; j < N; j++)
			mx[i][j] = (i == j) ? H[i] : max(mx[i][j - 1], H[j]);
	for (int j = 0; j < N; j++)
		for (int i = j; i >= 0; i--)
			p[i][j] = (i == j) ? H[i] : (p[i + 1][j] + mx[i][j]);
	for (int i = 0; i < N; i++)
		for (int j = i; j < N; j++)
			s[i][j] = (i == j) ? H[i] : (s[i][j - 1] + mx[i][j]);
	for (int i = 0; i < Q; i++) {
		int l = L[i], r = R[i];
		ll res = 1e18;
		for (int i = l; i <= r; i++)
			res = min(res, p[l][i] + s[i][r] - H[i]);
		C[i] = res;
	}
  }	else {
	  build(1, 1, N);
	  for (int i = 0; i < Q; i++) {
		  int l = L[i], r = R[i];
		  l++, r++;
		  C[i] = 2 * (r - l + 1) - getans(l, r);
	  }
  }
  return C;
}

Compilation message

meetings.cpp: In function 'void build(int, int, int)':
meetings.cpp:48:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = l + r >> 1;
          ~~^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 202 ms 124920 KB Output is correct
3 Correct 198 ms 124792 KB Output is correct
4 Correct 199 ms 124792 KB Output is correct
5 Correct 204 ms 124792 KB Output is correct
6 Correct 196 ms 124792 KB Output is correct
7 Correct 197 ms 124792 KB Output is correct
8 Correct 198 ms 124708 KB Output is correct
9 Correct 205 ms 124792 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 202 ms 124920 KB Output is correct
3 Correct 198 ms 124792 KB Output is correct
4 Correct 199 ms 124792 KB Output is correct
5 Correct 204 ms 124792 KB Output is correct
6 Correct 196 ms 124792 KB Output is correct
7 Correct 197 ms 124792 KB Output is correct
8 Correct 198 ms 124708 KB Output is correct
9 Correct 205 ms 124792 KB Output is correct
10 Correct 632 ms 301560 KB Output is correct
11 Correct 844 ms 301560 KB Output is correct
12 Correct 658 ms 301492 KB Output is correct
13 Correct 834 ms 301604 KB Output is correct
14 Correct 653 ms 301560 KB Output is correct
15 Correct 663 ms 301556 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 47 ms 2688 KB Output is correct
3 Correct 126 ms 11128 KB Output is correct
4 Correct 125 ms 11000 KB Output is correct
5 Correct 94 ms 11000 KB Output is correct
6 Correct 120 ms 11000 KB Output is correct
7 Correct 128 ms 11000 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 47 ms 2688 KB Output is correct
3 Correct 126 ms 11128 KB Output is correct
4 Correct 125 ms 11000 KB Output is correct
5 Correct 94 ms 11000 KB Output is correct
6 Correct 120 ms 11000 KB Output is correct
7 Correct 128 ms 11000 KB Output is correct
8 Incorrect 134 ms 11000 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 202 ms 124920 KB Output is correct
3 Correct 198 ms 124792 KB Output is correct
4 Correct 199 ms 124792 KB Output is correct
5 Correct 204 ms 124792 KB Output is correct
6 Correct 196 ms 124792 KB Output is correct
7 Correct 197 ms 124792 KB Output is correct
8 Correct 198 ms 124708 KB Output is correct
9 Correct 205 ms 124792 KB Output is correct
10 Correct 632 ms 301560 KB Output is correct
11 Correct 844 ms 301560 KB Output is correct
12 Correct 658 ms 301492 KB Output is correct
13 Correct 834 ms 301604 KB Output is correct
14 Correct 653 ms 301560 KB Output is correct
15 Correct 663 ms 301556 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 47 ms 2688 KB Output is correct
18 Correct 126 ms 11128 KB Output is correct
19 Correct 125 ms 11000 KB Output is correct
20 Correct 94 ms 11000 KB Output is correct
21 Correct 120 ms 11000 KB Output is correct
22 Correct 128 ms 11000 KB Output is correct
23 Incorrect 134 ms 11000 KB Output isn't correct
24 Halted 0 ms 0 KB -