Submission #484365

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
484365	2021-11-03T03:28:30 Z	melon940925	Aliens (IOI16_aliens)	C++14	Compilation error	0 ms	0 KB

aliens

#include "aliens.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
pii aliens[500001];
ll dp[500001];
ll Q[500001];
ll candidates[500001];
ll numOfArea[500001];
ll front, rear;
typedef long long ll;
ll N, K;
ll cost(ll a, ll b) {
	return (aliens[b].x - aliens[a].y) * (aliens[b].x - aliens[a].y);
}

ll func(ll i, ll j) {
	return dp[i] + cost(i + 1, j);
}

ll cross(ll i, ll j) {
	ll l = j + 1, r = N + 1;
	while (l > r) {
		ll m = l + r >> 1;
		if (func(i, m) <= func(j, m))l = m + 1;
		else r = m;
	}
	return l - 1;
}

void monotoneQueueOpt(ll m) {
	front = 0, rear = 1, Q[0] = 0, candidates[0] = N;
	for (int i = 1; i <= N; ++i) {
		while (candidates[front] < i)front++;
		dp[i] = func(Q[front], i) + m;
		numOfArea[i] = numOfArea[Q[front]] + 1;
		while (front + 1 < rear && cross(Q[rear - 1], i) < candidates[rear-2])rear--;
		candidates[rear] = N, candidates[rear - 1] = cross(Q[rear - 1], i), Q[rear++] = i;
	}
}

ll bs(ll l, ll r) {
	if (l >= r)return l;
	ll mid = l + r >> 1;
	monotoneQueueOpt(mid);
	if (numOfArea[N] > K)return bs(mid + 1, r);
	return bs(l, mid);
}

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
	//preprocess
	N = n, K = k;
	vector<pii> tmpAliens;
	for (int i = 0; i < n; ++i) {
		int x = r[i], y = c[i];
		if (x < y)swap(x, y);
		tmpAliens.push_back({ x,y });
	}
	sort(tmpAliens.begin(), tmpAliens.end(), [](const pii& a, const pii& b) {
		if (a.y == b.y)return a.x > b.x;
		return a.y < b.y;
		});
	pii prv = { -1,-1 };
	int idx = 0;
	for (auto& i : tmpAliens) {
		if (prv.y <= i.y && i.x <= prv.x)continue;
		prv = i;
		aliens[++idx] = i;
	}
	//preprocess end
	ll M = bs(0, 1e14);
	monotoneQueueOpt(M);
	return dp[n] - M * K;
}

Compilation message

aliens.cpp:8:1: error: 'll' does not name a type
    8 | ll dp[500001];
      | ^~
aliens.cpp:9:1: error: 'll' does not name a type
    9 | ll Q[500001];
      | ^~
aliens.cpp:10:1: error: 'll' does not name a type
   10 | ll candidates[500001];
      | ^~
aliens.cpp:11:1: error: 'll' does not name a type
   11 | ll numOfArea[500001];
      | ^~
aliens.cpp:12:1: error: 'll' does not name a type
   12 | ll front, rear;
      | ^~
aliens.cpp: In function 'll func(ll, ll)':
aliens.cpp:20:9: error: 'dp' was not declared in this scope
   20 |  return dp[i] + cost(i + 1, j);
      |         ^~
aliens.cpp: In function 'll cross(ll, ll)':
aliens.cpp:26:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |   ll m = l + r >> 1;
      |          ~~^~~
aliens.cpp: In function 'void monotoneQueueOpt(ll)':
aliens.cpp:34:2: error: 'front' was not declared in this scope
   34 |  front = 0, rear = 1, Q[0] = 0, candidates[0] = N;
      |  ^~~~~
aliens.cpp:34:13: error: 'rear' was not declared in this scope
   34 |  front = 0, rear = 1, Q[0] = 0, candidates[0] = N;
      |             ^~~~
aliens.cpp:34:23: error: 'Q' was not declared in this scope
   34 |  front = 0, rear = 1, Q[0] = 0, candidates[0] = N;
      |                       ^
aliens.cpp:34:33: error: 'candidates' was not declared in this scope
   34 |  front = 0, rear = 1, Q[0] = 0, candidates[0] = N;
      |                                 ^~~~~~~~~~
aliens.cpp:37:3: error: 'dp' was not declared in this scope
   37 |   dp[i] = func(Q[front], i) + m;
      |   ^~
aliens.cpp:38:3: error: 'numOfArea' was not declared in this scope
   38 |   numOfArea[i] = numOfArea[Q[front]] + 1;
      |   ^~~~~~~~~
aliens.cpp: In function 'll bs(ll, ll)':
aliens.cpp:46:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |  ll mid = l + r >> 1;
      |           ~~^~~
aliens.cpp:48:6: error: 'numOfArea' was not declared in this scope
   48 |  if (numOfArea[N] > K)return bs(mid + 1, r);
      |      ^~~~~~~~~
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:75:9: error: 'dp' was not declared in this scope
   75 |  return dp[n] - M * K;
      |         ^~