oj.uz

Submission #73210

# Submission time Handle Problem Language Result Execution time Memory
73210 2018-08-28T04:51:01 Z 윤교준(#2271) Circus (Balkan15_CIRCUS) C++11
100 / 100
 1304 ms 11580 KB 
#include "circus.h"
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 100005;

vector<pii> VA, VB;

int A[MAXN], B[MAXN], C[MAXN];

int N, M;

void init(int N, int M, int P[]) {
	::N = N; ::M = M;
	for(int i = 1; i <= N; i++) A[i] = P[i-1];
	sort(A+1, A+N+1);
	for(int i = 1; i <= N; i++) B[i] = M - A[i];

	for(int t = 0; t < 35; t++) {
		fill(C, C+N+1, -INF);
		for(int i = 1; i <= N; i++) {
			upmax(C[i], C[i-1]);
			if(0 <= C[i]) upmin(B[i], A[i] - C[i]);
			int j = int(lower_bound(A+1, A+N+1, A[i]+B[i]) - A);
			upmax(C[j], A[i]);
		}
		fill(C, C+N+2, INF);
		for(int i = N; i; i--) {
			upmin(C[i], C[i+1]);
			if(C[i] < INF) upmin(B[i], C[i] - A[i]);
			int j = int(upper_bound(A+1, A+N+1, A[i]-B[i]) - A) - 1;
			upmin(C[j], A[i]);
		}
	}
	
	for(int i = 1, x; i <= N; i++) {
		x = A[i]-B[i];
		if(!VA.empty() && x <= VA.back().first) continue;
		VA.eb(x, A[i]);
	}
	for(int i = N, x; i; i--) {
		x = A[i]+B[i];
		if(!VB.empty() && VB.back().first <= x) continue;
		VB.eb(x, A[i]);
	}
	revv(VB);
}

int minLength(int X) {
	int ret = M - X;
	if(X <= VA.back().first) {
		int j = int(lower_bound(allv(VA), pii(X, -INF)) - VA.begin());
		upmin(ret, VA[j].second - X);
	}
	if(VB[0].first <= X) {
		int j = int(upper_bound(allv(VB), pii(X, INF)) - VB.begin()) - 1;
		upmin(ret, X - VB[j].second);
	}
	return ret;
}

Compilation message

grader.cpp: In function 'int main()':
grader.cpp:14:12: warning: unused variable 'max_code' [-Wunused-variable]
  long long max_code;
            ^~~~~~~~
grader.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
grader.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &P[i]);
   ~~~~~^~~~~~~~~~~~~
grader.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
grader.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &d);
   ~~~~~^~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 3424 KB Output is correct
2 Correct 457 ms 3508 KB Output is correct
3 Correct 449 ms 3508 KB Output is correct
4 Correct 450 ms 3536 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3536 KB Output is correct
2 Correct 3 ms 3536 KB Output is correct
3 Correct 3 ms 3536 KB Output is correct
4 Correct 3 ms 3536 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3536 KB Output is correct
2 Correct 3 ms 3536 KB Output is correct
3 Correct 3 ms 3536 KB Output is correct
4 Correct 3 ms 3536 KB Output is correct
5 Correct 12 ms 3536 KB Output is correct
6 Correct 11 ms 3536 KB Output is correct
7 Correct 10 ms 3536 KB Output is correct
8 Correct 10 ms 3536 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3536 KB Output is correct
2 Correct 3 ms 3536 KB Output is correct
3 Correct 3 ms 3536 KB Output is correct
4 Correct 3 ms 3536 KB Output is correct
5 Correct 12 ms 3536 KB Output is correct
6 Correct 11 ms 3536 KB Output is correct
7 Correct 10 ms 3536 KB Output is correct
8 Correct 10 ms 3536 KB Output is correct
9 Correct 543 ms 8464 KB Output is correct
10 Correct 532 ms 8464 KB Output is correct
11 Correct 454 ms 8464 KB Output is correct
12 Correct 585 ms 9252 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 3424 KB Output is correct
2 Correct 457 ms 3508 KB Output is correct
3 Correct 449 ms 3508 KB Output is correct
4 Correct 450 ms 3536 KB Output is correct
5 Correct 4 ms 3536 KB Output is correct
6 Correct 3 ms 3536 KB Output is correct
7 Correct 3 ms 3536 KB Output is correct
8 Correct 3 ms 3536 KB Output is correct
9 Correct 12 ms 3536 KB Output is correct
10 Correct 11 ms 3536 KB Output is correct
11 Correct 10 ms 3536 KB Output is correct
12 Correct 10 ms 3536 KB Output is correct
13 Correct 454 ms 9252 KB Output is correct
14 Correct 468 ms 9252 KB Output is correct
15 Correct 487 ms 9252 KB Output is correct
16 Correct 472 ms 9252 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 3424 KB Output is correct
2 Correct 457 ms 3508 KB Output is correct
3 Correct 449 ms 3508 KB Output is correct
4 Correct 450 ms 3536 KB Output is correct
5 Correct 4 ms 3536 KB Output is correct
6 Correct 3 ms 3536 KB Output is correct
7 Correct 3 ms 3536 KB Output is correct
8 Correct 3 ms 3536 KB Output is correct
9 Correct 12 ms 3536 KB Output is correct
10 Correct 11 ms 3536 KB Output is correct
11 Correct 10 ms 3536 KB Output is correct
12 Correct 10 ms 3536 KB Output is correct
13 Correct 543 ms 8464 KB Output is correct
14 Correct 532 ms 8464 KB Output is correct
15 Correct 454 ms 8464 KB Output is correct
16 Correct 585 ms 9252 KB Output is correct
17 Correct 454 ms 9252 KB Output is correct
18 Correct 468 ms 9252 KB Output is correct
19 Correct 487 ms 9252 KB Output is correct
20 Correct 472 ms 9252 KB Output is correct
21 Correct 1213 ms 9252 KB Output is correct
22 Correct 1304 ms 9252 KB Output is correct
23 Correct 1101 ms 10400 KB Output is correct
24 Correct 1177 ms 11580 KB Output is correct