oj.uz

Submission #211797

# Submission time Handle Problem Language Result Execution time Memory
211797 2020-03-21T09:54:10 Z cgiosy Holiday (IOI14_holiday) C++17
100 / 100
 250 ms 43776 KB 
#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;
using ll=long long;

struct pst {
	struct T { ll x=0; int cnt=0, l=0, r=0; };
	int N, id=0, td=0;
	vector<T> A;
	vector<int> D, X;
	pst(vector<int>&& _): N(_.size()), A(1800000), D(N+1), X(move(_)) {}
	void add(int x, int s, int e, int&i) {
		int p=i; i=++id;
		A[i]={A[p].x+X[x], A[p].cnt+1, A[p].l, A[p].r};
		if(s==e) return;
		int m=s+e>>1;
		if(x<=m) add(x, s, m, A[i].l);
		else add(x, m+1, e, A[i].r);
	}
	void add(int x) { td++; add(x, 0, N-1, D[td]=D[td-1]); }
	ll sum(int k, int s, int e, int i, int j) {
		if(A[j].cnt-A[i].cnt<=k) return A[j].x-A[i].x;
		if(s==e) return X[s]*ll(k);
		int m=s+e>>1, n=A[A[j].r].cnt-A[A[i].r].cnt;
		if(k<=n) return sum(k, m+1, e, A[i].r, A[j].r);
		else return sum(k-n, s, m, A[i].l, A[j].l)+A[A[j].r].x-A[A[i].r].x;
	}
	ll sum(int l, int r, int k) {
		return sum(k, 0, N-1, D[l], D[r+1]);
	}
};
ll findMaxAttraction(int N, int st, int M, int A[]) {
	vector<int> X(A, A+N);
	sort(begin(X), end(X));
	for(int i=0; i<N; i++) A[i]=lower_bound(begin(X), end(X), A[i])-begin(X);
	pst t(move(X));
	for(int i=0; i<N; i++) t.add(A[i]);
	function<ll(int, int, int, int)> f=[&](int s, int e, int l, int r) {
		if(s>e || l>r) return ll(0);
		int m=s+e>>1;
		pair<ll, int> n={-1, -1};
		for(int i=l; i<=r; i++)
			n=max(n, {t.sum(m, i, M+m-i-min(i-st, st-m)), i});
		return max({n.first, f(s, m-1, l, n.second), f(m+1, e, n.second, r)});
	};
	return f(max(st-M, 0), st, st, min(st+M, N-1));
}

Compilation message

holiday.cpp: In member function 'void pst::add(int, int, int, int&)':
holiday.cpp:16:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m=s+e>>1;
         ~^~
holiday.cpp: In member function 'll pst::sum(int, int, int, int, int)':
holiday.cpp:24:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m=s+e>>1, n=A[A[j].r].cnt-A[A[i].r].cnt;
         ~^~
holiday.cpp: In lambda function:
holiday.cpp:40:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m=s+e>>1;
         ~^~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 42624 KB Output is correct
2 Correct 25 ms 42624 KB Output is correct
3 Correct 25 ms 42624 KB Output is correct
4 Correct 26 ms 42624 KB Output is correct
5 Correct 27 ms 42624 KB Output is correct
6 Correct 27 ms 42624 KB Output is correct
7 Correct 26 ms 42616 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 43768 KB Output is correct
2 Correct 54 ms 43776 KB Output is correct
3 Correct 54 ms 43768 KB Output is correct
4 Correct 52 ms 43768 KB Output is correct
5 Correct 70 ms 43736 KB Output is correct
6 Correct 37 ms 43000 KB Output is correct
7 Correct 46 ms 43128 KB Output is correct
8 Correct 53 ms 43256 KB Output is correct
9 Correct 32 ms 42880 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 42624 KB Output is correct
2 Correct 26 ms 42624 KB Output is correct
3 Correct 28 ms 42624 KB Output is correct
4 Correct 27 ms 42624 KB Output is correct
5 Correct 28 ms 42624 KB Output is correct
6 Correct 26 ms 42624 KB Output is correct
7 Correct 26 ms 42624 KB Output is correct
8 Correct 26 ms 42624 KB Output is correct
9 Correct 25 ms 42624 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 43768 KB Output is correct
2 Correct 63 ms 43768 KB Output is correct
3 Correct 70 ms 43128 KB Output is correct
4 Correct 27 ms 42624 KB Output is correct
5 Correct 26 ms 42624 KB Output is correct
6 Correct 27 ms 42624 KB Output is correct
7 Correct 25 ms 42624 KB Output is correct
8 Correct 245 ms 43772 KB Output is correct
9 Correct 250 ms 43768 KB Output is correct