Submission #1105222

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105222		vako_p	Measures (CEOI22_measures)	C++14	0 / 100	1544 ms	45224 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int mxN = 1e6 + 5;
ll n,a[mxN],b[mxN],d,n1,m,idx[mxN];
map<ll,ll> idx1;
set<ll> ss;

struct segtree{
	vector<ll> v,p,s,cnt;	
	ll sz = 1;
	
	void init(){
		while(sz < n) sz *= 2;
		v.assign(2 * sz, 0LL);
		p.assign(2 * sz, -1e10);
		s.assign(2 * sz, -1e10);
		cnt.assign(2 * sz, 0LL);
	}
	
	void set(ll i, ll x, ll lx, ll rx){
		if(rx - lx == 1){
			s[x] = -idx[min(i + 1, n - 1)] + idx[i] + cnt[x] * d;
			p[x] = cnt[x] * d; 
			v[x] = cnt[x] * d;
			cnt[x]++;
//			if(i == 2) cout << i << ' ' << lx << ' ' << rx << "---> " << p[x] << ' ' << s[x] << " : " << v[x] << '\n';
			return;
		}
		ll mid = lx + (rx - lx) / 2;
		if(i < mid) set(i, 2 * x + 1, lx, mid);
		else set(i, 2 * x + 2, mid, rx);
		cnt[x] = cnt[2 * x + 1] + cnt[2 * x + 2];
		v[x] = max(v[2 * x + 1] , v[2 * x + 2]);
		s[x] = s[2 * x + 2];
		p[x] = p[2 * x + 1];
		if(cnt[2 * x + 1] and cnt[2 * x + 2]) v[x] = max(v[x], d + s[2 * x + 1] + p[2 * x + 2]);
		p[x] = max(p[x], p[2 * x + 2] - (idx[mid] - idx[lx]) + cnt[2 * x + 1] * d);
		s[x] = max(s[x], s[2 * x + 1] - (idx[min(rx, n - 1)] - idx[mid]) + cnt[2 * x + 2] * d);
//		if(i == 2) cout << i << ' ' << lx << ' ' << rx << "---> " << p[x] << ' ' << s[x] << " : " << v[x] << '\n';
	}
	
	void set(ll i){
		set(i, 0, 0, sz);
	}
	
	ll find(){
		return v[0]; 
	}
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n1 >> m >> d;
	for(int i = 0; i < n1; i++){
		cin >> a[i];
		ss.insert(a[i]);
	}
	for(int i = 0; i < m; i++){
		cin >> b[i];
		ss.insert(b[i]);
	}
	ll cc = 0;
	for(auto it : ss){
		idx1[it] = cc;
		idx[cc++] = it;
	}
//	idx[cc] = 2e9;
	n = ss.size();
	segtree s;
	s.init();
	
	vector<ll> vv;
	
	for(int i = 0; i < n1; i++){
		s.set(idx1[a[i]]);
		vv.pb(a[i]);
//		cout << a[i] << ' ' << idx1[a[i]] << ' ' << s.find() << '\n'; 	
	}
	for(int i = 0; i < m; i++){
		s.set(idx1[b[i]]);
		vv.pb(b[i]);
		sort(vv.begin(), vv.end());
		ll ans = 0;
		for(int j = 1; j < vv.size(); j++){
			ll x = 0;
			for(int k = j - 1; k >= 0; k--){
				x += d;
				ans = max(ans, x - vv[j] + vv[k]);
			}
		}
		assert(ans == s.find());
		cout << (double)s.find() / 2 << ' ';
	}
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:89:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |   for(int j = 1; j < vv.size(); j++){
      |                  ~~^~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 35
• Subtask 4: 0 / 41