oj.uz

Submission #147343

# Submission time Handle Problem Language Result Execution time Memory
147343 2019-08-29T01:18:14 Z TAMREF Holiday (IOI14_holiday) C++11
100 / 100
 1140 ms 5748 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int a[100005];
int n, st, d;
vector<int> cmp;
 
struct Segtree{
	ll seg[262500];
	int cnt[262500];
	void init(){
		memset(seg, 0, sizeof(seg));
		memset(cnt, 0, sizeof(cnt));
	}
	void upd(int now, int s, int e, int i, int v){
		if(i < s || i > e) return;
		cnt[now] += v;
		seg[now] += v * cmp[i];
		if(s == e) return;
		int m = s + e >> 1;
		upd(now << 1, s, m, i, v);
		upd(now << 1 | 1, m+1, e, i, v);
	}
	ll sum_max_kth(int now, int s, int e, int k){
		if(!k) return 0;
		if(s == e) return ll(min(cnt[now], k)) * cmp[s];
		int m = s + e >> 1;
		if(cnt[now << 1 | 1] > k) return sum_max_kth(now<<1|1, m+1, e, k);
		else return sum_max_kth(now << 1, s, m, k - cnt[now<<1|1]) + seg[now<<1|1];
	}
} S;
 
map<int, int> M;
bool chk[100005];
void upd(int i, int v){
	if((v == 1) == chk[i]) return;
	//cout << (v == 1 ? "Add " : "Rmv ") << i << "(val = " << cmp[a[i]] << ")\n";
	chk[i] ^= 1;
	/*
	M[cmp[a[i]]] += v;
	if(!M[cmp[a[i]]]) M.erase(cmp[a[i]]);
	int summ = 0, cntt = 0;
	for(auto p : M) summ += p.first * p.second, cntt += p.second;
	for(auto p : M){
		summ -= p.first * p.second;
		cntt -= p.second;
		cout << p.first << ' ' << cntt << ' ' << summ << '\n';
	}
	*/
	S.upd(1, 0, (int)cmp.size() - 1, a[i], v);
}
 
ll qry(int k){
	ll qv = S.sum_max_kth(1, 0, (int)cmp.size() - 1, k);
	//cout << "k = " << k << ", qry = " << qv << "\n";
	return qv;
}
 
void init(int N, int S, int D, int A[]){
	n = N; st = S; d = D;
	for(int i = 0; i < n; i++){
      	a[i] = A[i];
		cmp.push_back(a[i]);
	}
	sort(cmp.begin(), cmp.end());
	cmp.erase( unique(cmp.begin(),cmp.end()), cmp.end() );
	for(int i = 0; i < n; i++){
		a[i] = lower_bound(cmp.begin(), cmp.end(), a[i]) - cmp.begin();
	}
}
 
ll ans;
 
void dnc(int s, int e, int kmin, int kmax){ //(e, kmin) maintains painted
	//cout << "dnc([" << s << "," << e << "], [" << kmin << "," << kmax << "])\n";
	if(s > e) return;
	int m = s + e >> 1;
	//cout << "m = " << m << "\n";
	for(int i = m; i <= e; i++) upd(i, 1);
	int klim = min(kmax, 2*m + d - st);
	ll lans = 0;
	int lansi = kmin;
	for(int i = kmin; i <= klim; i++){
		//cout << "i = " << i << ", slot = " << 2*m + d - (st+i) << "\n";
		upd(i, 1);
		ll tmp = qry(d - (st-m) - (i-m));
		if(tmp > lans){
			lans = tmp;
			lansi = i;
		}
	}
	ans = max(ans, lans);
	for(int i = klim; i >= lansi; i--) upd(i, -1);
	if(m < e){
		int mm = (m+1+e) >> 1;
		for(int i = m; i <= mm; i++) upd(i, -1);
		dnc(m+1, e, lansi, kmax);
	}
	for(int i = kmax; i >= kmin; i--) upd(i, -1);
	if(s < m){
		int ss = (s+m-1) >> 1;
		for(int i = m; i < min(kmin, e+1); i++) upd(i, 1);
		dnc(s, m-1, kmin, lansi);
		for(int i = ss; i <= e; i++) upd(i, -1);
	}
	for(int i = m; i <= e; i++) upd(i, -1);
	for(int i = kmin; i <= lansi; i++) upd(i, -1);
}
 
void pro(){
	//cout << "pro\n";
	S.init();
	memset(chk,0,sizeof(chk));
	
	//M.clear();
	
	int l = max(0, st - d);
	dnc(l, st, st, n-1);
}
 
ll findMaxAttraction(int N, int S, int D, int A[]){
	ios_base::sync_with_stdio(0); cin.tie(0);
	init(N, S, D, A);
	pro();
	reverse(a, a+n); st = n-1-st;
	pro();
	return ans;
}

Compilation message

holiday.cpp: In member function 'void Segtree::upd(int, int, int, int, int)':
holiday.cpp:21:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s + e >> 1;
           ~~^~~
holiday.cpp: In member function 'll Segtree::sum_max_kth(int, int, int, int)':
holiday.cpp:28:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s + e >> 1;
           ~~^~~
holiday.cpp: In function 'void dnc(int, int, int, int)':
holiday.cpp:78:12: 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 5 ms 3576 KB Output is correct
2 Correct 5 ms 3576 KB Output is correct
3 Correct 5 ms 3576 KB Output is correct
4 Correct 5 ms 3576 KB Output is correct
5 Correct 5 ms 3448 KB Output is correct
6 Correct 5 ms 3576 KB Output is correct
7 Correct 5 ms 3576 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 4980 KB Output is correct
2 Correct 40 ms 4980 KB Output is correct
3 Correct 61 ms 4980 KB Output is correct
4 Correct 58 ms 4980 KB Output is correct
5 Correct 221 ms 4980 KB Output is correct
6 Correct 67 ms 4088 KB Output is correct
7 Correct 120 ms 4472 KB Output is correct
8 Correct 154 ms 4600 KB Output is correct
9 Correct 50 ms 3960 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3576 KB Output is correct
2 Correct 6 ms 3576 KB Output is correct
3 Correct 12 ms 3576 KB Output is correct
4 Correct 20 ms 3576 KB Output is correct
5 Correct 19 ms 3576 KB Output is correct
6 Correct 8 ms 3576 KB Output is correct
7 Correct 8 ms 3580 KB Output is correct
8 Correct 9 ms 3576 KB Output is correct
9 Correct 8 ms 3580 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 5748 KB Output is correct
2 Correct 387 ms 5748 KB Output is correct
3 Correct 201 ms 4600 KB Output is correct
4 Correct 18 ms 3576 KB Output is correct
5 Correct 8 ms 3576 KB Output is correct
6 Correct 8 ms 3576 KB Output is correct
7 Correct 8 ms 3576 KB Output is correct
8 Correct 1140 ms 5628 KB Output is correct
9 Correct 1129 ms 5620 KB Output is correct