제출 #246818

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
246818		srvlt	모임들 (IOI18_meetings)	C++14	19 / 100	5551 ms	302048 KiB

meetings

#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, n3 = 2e6 + 123;
int mx[n][n], h[n2], m, ind[22][n2], lg[n2];
ll p[n][n], s[n][n], dp[n3];

struct Node {
	int l = 0, r = 0, val = 0;
	vector <int> v;
	vector <ll> sp[17];
	void build() {
		int s = SZ(v);
		for (int i = 0; i < 17; i++)
			sp[i].resize(s);
		for (int i = 0; i < s; i++)
			sp[0][i] = dp[v[i]];
		for (int i = 1; i < 17; i++)
			for (int j = 0; j + (1 << i) - 1 < s; j++)
				sp[i][j] = max(sp[i - 1][j], sp[i - 1][j + (1 << (i - 1))]);
	}
	ll get(int l, int r) {
		int len = lg[r - l + 1];
		return max(sp[len][l], sp[len][r - (1 << len) + 1]);
	}
};
vector <Node> t;

int pos(int v, int x) {
	int s = SZ(t[v].v);
	int L = 0, R = s;
	while (L < R - 1) {
		int mid = L + R >> 1;
		if (t[t[v].v[mid]].l <= x)
			L = mid;
		else
			R = mid;
	}
	if (t[v].v[L] > x) return -1;
	return L;
}

void dfs(int v) {
	dp[v] = 0;
	for (int i : t[v].v) {
		dfs(i);
		dp[v] = max(dp[v], dp[i]);
	}
	if (t[v].val < 21)
		dp[v] += t[v].r - t[v].l + 1;
}

ll get(int v, int l, int r) {
	if (t[v].r < l || t[v].l > r) return 0;
	if (t[v].l >= l && t[v].r <= r) return dp[v];
	ll res = 0;
	if (SZ(t[v].v)) {
		int a = pos(v, l), b = pos(v, r);
		if (a != -1) res = max(res, get(t[v].v[a], l, r));
		if (b != -1) res = max(res, get(t[v].v[b], l, r));
		int l2 = a + 1, r2 = b - 1;
		if (l2 <= r2)
			res = max(res, t[v].get(l2, r2));
	}
	if (t[v].val < 21)
		res += max(0, min(r, t[v].r) - max(l, t[v].l) + 1);
	return res;
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
	for (int i = 2; i < n2; i++)
		lg[i] = lg[i / 2] + 1;
  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 {
	  t.pb(Node());
	  for (int i = 21; i >= 2; i--) {
		  int last = -1;
		  for (int j = 0; j <= N; j++) {
			  if (j == N || h[j] >= i) {
				  if (last + 1 <= j - 1) {
					  t.pb(Node());
					  m++;
					  t[m].l = last + 1, t[m].r = j - 1;
					  for (int k = t[m].l; k <= t[m].r; k++)
						  ind[i][k] = m;
					  t[m].val = i;
					  if (i < 21)
						  t[ind[i + 1][j - 1]].v.pb(m);
				  }
				  last = j;
			  }
		  }
	  }
	  dfs(1);
	  for (int i = 1; i <= m; i++)
		t[i].build();
	  for (int i = 0; i < Q; i++) {
		  int l = L[i], r = R[i];
		  C[i] = (ll)20 * (r - l + 1) - get(1, l, r);
	  }
  }
  return C;
}

컴파일 시 표준 에러 (stderr) 메시지

meetings.cpp: In function 'int pos(int, int)':
meetings.cpp:44:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = L + R >> 1;
             ~~^~~

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