oj.uz

Submission #72115

# Submission time Handle Problem Language Result Execution time Memory
72115 2018-08-26T05:22:07 Z BBBSNG(#2263, youngyojun, sebinkim, dlalswp25) Box Run (FXCUP3_box) C++17
100 / 100
 205 ms 46236 KB 
#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
//#define rf(x) (x)=0;while(*p<48)im=*p=='-';while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);if(im)(x)=-(x);
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#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 cb(x) (x)=(!(x))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
#define INFST (0x7f7f7f7f)
#define INFLLST (0x7f7f7f7f7f7f7f7fll)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ld, ld> pdd;
typedef complex<ld> base;
const ld EPS = (ld)1e-7;
const ld PI = acos(0) * 2;
bool isZero(const ld& x) { return abs(x) <= EPS; }
int sign(const ld& x) { return isZero(x) ? 0 : (0 < x ? 1 : -1); }
ll gcd(ll a, ll b) { for(;b;a%=b,swap(a,b)){} return abs(a); }
pll operator + (const pll& a, const pll& b) { return pll(a.first+b.first, a.second+b.second); }
pll operator - (const pll& a, const pll& b) { return pll(a.first-b.first, a.second-b.second); }
pll operator * (const pll& a, const ll& b) { return pll(a.first*b, a.second*b); }
ll operator * (const pll& a, const pll& b) { return a.first*b.second - b.first*a.second; }
ll ccw(const pll& a, const pll& b, const pll& c) { return a*b + b*c + c*a; }
void fg(vector<int> G[], int a, int b) { G[a].pb(b); G[b].pb(a); }
void fg(vector<pii> G[], int a, int b, int c) { G[a].pb({b, c}); G[b].pb({a, c}); }

const int MAXN = 500005;

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

int N;

int main() {
	ios::sync_with_stdio(false);

	cin >> N;
	for(int i = 1; i <= N; i++) cin >> A[i];
	for(int i = 1; i <= N; i++) B[0][i] = A[i];
	for(int j = 1; j < 19; j++) {
		for(int i = 1; i <= N; i++) {
			B[j][i] = B[j-1][i];
			if(0 < i - (1 << (j-1)))
				upmax(B[j][i], B[j-1][i - (1<<(j-1))]);
		}
	}

	for(int i = 2; i <= N; i++) {
		if(A[i-1] >= A[i]) continue;
		int j = i-1;
		for(int k = 19; k--;) {
			if(j - (1 << k) + 1 <= 0) continue;
			if(B[k][j] < A[i]) {
				j -= 1 << k;
				j++;
			}
		}
		for(; j < i && A[j] >= A[i]; j++);
		for(; 1 < j && A[j-1] < A[i]; j--);
		C[i] = i - j;
	}

	for(int i = 1, j = 1; i <= N; i++) if(C[i]) {
		for(; j <= C[i]; j++) D[j] = i;
	}
	for(int i = 1; i <= N; i++) {
		if(!D[i]) {
			printf("-1 ");
			continue;
		}
		printf("%d ", D[i] - i);
	}
	puts("");
	return 0;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 2 ms 564 KB Output is correct
4 Correct 2 ms 564 KB Output is correct
5 Correct 2 ms 624 KB Output is correct
6 Correct 3 ms 672 KB Output is correct
7 Correct 3 ms 672 KB Output is correct
8 Correct 2 ms 672 KB Output is correct
9 Correct 2 ms 800 KB Output is correct
10 Correct 3 ms 800 KB Output is correct
11 Correct 2 ms 800 KB Output is correct

Subtask #2
83.0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 2 ms 564 KB Output is correct
4 Correct 2 ms 564 KB Output is correct
5 Correct 2 ms 624 KB Output is correct
6 Correct 3 ms 672 KB Output is correct
7 Correct 3 ms 672 KB Output is correct
8 Correct 2 ms 672 KB Output is correct
9 Correct 2 ms 800 KB Output is correct
10 Correct 3 ms 800 KB Output is correct
11 Correct 2 ms 800 KB Output is correct
12 Correct 2 ms 824 KB Output is correct
13 Correct 3 ms 1196 KB Output is correct
14 Correct 20 ms 4832 KB Output is correct
15 Correct 27 ms 7416 KB Output is correct
16 Correct 50 ms 9860 KB Output is correct
17 Correct 116 ms 24128 KB Output is correct
18 Correct 202 ms 32548 KB Output is correct
19 Correct 163 ms 40988 KB Output is correct
20 Correct 194 ms 46236 KB Output is correct
21 Correct 205 ms 46236 KB Output is correct