oj.uz

Submission #78975

# Submission time Handle Problem Language Result Execution time Memory
78975 2018-10-10T02:58:34 Z tmwilliamlin168 Holiday (IOI14_holiday) C++14
100 / 100
 760 ms 8436 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mxN=1e5;
int n, s, d, *a, p[mxN], b[mxN], cl;
ll ans, c1[2*mxN+mxN/2+1], c2[2*mxN+mxN/2+1];
array<ll, 2> ft[mxN+1];
vector<int> v;

void upd(int i, array<ll, 2> x) {
	for(++i; i<=n; i+=i&-i) {
		ft[i][0]+=x[0];
		ft[i][1]+=x[1];
	}
}

void ml(int nl) {
	while(cl<nl) {
		++cl;
		if(v[cl]!=-1)
			upd(b[v[cl]], {1, a[v[cl]]});
	}
	while(cl>nl) {
		if(v[cl]!=-1)
			upd(b[v[cl]], {-1, -a[v[cl]]});
		--cl;
	}
}

void s3(int l1, int r1, int l2, int r2, ll c[2*mxN+mxN/2+1]) {
	if(l1>r1)
		return;
	int m1=(l1+r1)/2;
	array<ll, 2> m2{-1};
	for(int i=l2; i<=r2; ++i) {
		ml(i);
		ll s2=0;
		for(int j=16, lb=0, s1=0; j>=0; --j) {
			if(lb+(1<<j)<=n&&s1+ft[lb+(1<<j)][0]<=m1-i) {
				lb+=1<<j;
				s1+=ft[lb][0];
				s2+=ft[lb][1];
			}
		}
		m2=max(array<ll, 2>{s2, -i}, m2);
	}
	c[m1]=m2[0];
	s3(l1, m1-1, l2, -m2[1], c);
	s3(m1+1, r1, -m2[1], r2, c);
}

void s2(ll c[2*mxN+mxN/2+1]) {
	memset(ft, 0, sizeof(ft));
	cl=-1;
	s3(0, d, 0, v.size()-1, c);
	v.clear();
}

void s1() {
	sort(p, p+n, [&](const int &i, const int &j) {
		return a[i]>a[j];
	});
	for(int i=0; i<n; ++i)
		b[p[i]]=i;
	for(int i=s; i>=0; --i)
		v.push_back(i);
	s2(c1);
	v.push_back(-1);
	for(int i=s+1; i<n; ++i) {
		v.push_back(-1);
		v.push_back(i);
	}
	s2(c2);
	for(int i=0; i<=d; ++i)
		ans=max(c1[i]+c2[d-i], ans);
}

ll findMaxAttraction(int n2, int s2, int d2, int a2[]) {
	n=n2;
	s=s2;
	d=d2;
	a=a2;
	for(int i=0; i<n; ++i)
		p[i]=i;
	s1();
	s=n-1-s;
	for(int i=0; i<n-1-i; ++i)
		swap(a[i], a[n-1-i]);
	s1();
    return ans;
}

Compilation message

grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1916 KB Output is correct
2 Correct 3 ms 1916 KB Output is correct
3 Correct 4 ms 1984 KB Output is correct
4 Correct 4 ms 2188 KB Output is correct
5 Correct 3 ms 2188 KB Output is correct
6 Correct 4 ms 2188 KB Output is correct
7 Correct 3 ms 2188 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 599 ms 7376 KB Output is correct
2 Correct 531 ms 7436 KB Output is correct
3 Correct 597 ms 7436 KB Output is correct
4 Correct 521 ms 7496 KB Output is correct
5 Correct 725 ms 7496 KB Output is correct
6 Correct 240 ms 7496 KB Output is correct
7 Correct 382 ms 7496 KB Output is correct
8 Correct 453 ms 7496 KB Output is correct
9 Correct 186 ms 7496 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 7496 KB Output is correct
2 Correct 15 ms 7496 KB Output is correct
3 Correct 15 ms 7496 KB Output is correct
4 Correct 15 ms 7496 KB Output is correct
5 Correct 14 ms 7496 KB Output is correct
6 Correct 6 ms 7496 KB Output is correct
7 Correct 6 ms 7496 KB Output is correct
8 Correct 6 ms 7496 KB Output is correct
9 Correct 6 ms 7496 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 606 ms 8436 KB Output is correct
2 Correct 760 ms 8436 KB Output is correct
3 Correct 230 ms 8436 KB Output is correct
4 Correct 12 ms 8436 KB Output is correct
5 Correct 6 ms 8436 KB Output is correct
6 Correct 6 ms 8436 KB Output is correct
7 Correct 6 ms 8436 KB Output is correct
8 Correct 747 ms 8436 KB Output is correct
9 Correct 730 ms 8436 KB Output is correct