Submission #654333

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
654333	2022-10-31T02:56:10 Z	sunwukong123	Measures (CEOI22_measures)	C++14	100 / 100	906 ms	64404 KB

Main

#include <bits/stdc++.h>
using namespace std;
#define int ll 
#define FOR(i,s,e) for(ll i = s; i <= (ll)e; ++i)
#define DEC(i,s,e) for(ll i = s; i >= (ll)e; --i)
#define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
#define db(x) cerr << #x << "=" << x << "\n"
#define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n"
#define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n"
#define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n"
#define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{"  << ite.f << ',' << ite.s << "} "; cerr << "\n"
#define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n"
#else
#define db(x)
#define db2(x,y)
#define db3(a,b,c)
#define dbv(v)
#define dbvp(v)
#define dba(a,ss,ee)
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long 
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define f first 	
#define s second
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
#define g3(x) get<3>(x)
#define reach cerr << "LINE: " << __LINE__ << "\n";
typedef pair <ll, ll> pi;
typedef tuple<ll,ll,ll> ti3;
typedef tuple<ll,ll,ll,ll> ti4;
ll rand(ll a, ll b) { return a + rng() % (b-a+1); }
const int MOD = 1e9 + 7;
const int inf = (int)1e9 + 500;
const long long oo = (ll)1e18 + 500;
template <typename T> bool chmax(T& a, const T b) { return a<b ? a = b, 1 : 0; }
template <typename T> bool chmin(T& a, const T b) { return a>b ? a = b, 1 : 0; }
const int MAXN = 200015;
int n,m,d;
pi A[MAXN];
map<pi,int> where;

struct node {
	int s,e,m;
	int mxpre,mxsuf,mx,sum;
	node *l, *r;
	node (int _s, int _e) {
		s=_s;e=_e;
		m=(s+e)/2;
		mxpre=mxsuf=mx=sum=0;
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	void combi() {
		sum=l->sum+r->sum;
		mxpre=max(l->sum+r->mxpre, l->mxpre);
		mxsuf=max(r->sum+l->mxsuf, r->mxsuf);
		mx=max({sum,mxpre,mxsuf,l->mx,r->mx,l->mxsuf+r->mxpre});
	}
	void update(int x, int nval) {
		db2(x,nval);
		if(s==e) {
			sum=nval;
			mxpre=max(sum,0ll);
			mxsuf=max(sum,0ll);
			mx=max(sum,0ll);
			return;
		}
		if(x>m)r->update(x,nval);
		else l->update(x,nval);
		combi();
	}
	int get() {
		return mx;
	}
} *seg;
int B[MAXN];
 
int solve() {
	int mx=0;
	int ans=0;
	int D[n+2];
	FOR(i,1,n-1) {
		D[i]=B[i+1]-B[i];
		D[i] = d-D[i];
	}
	dba(D,1,n-1);
	FOR(i,1,n-1) {
		mx=max(mx+D[i],D[i]);
		chmax(ans,mx);
	}
	return ans;
}
int32_t main() 
{
	IAMSPEED
	cin >> n >> m >> d;
	if(n){
		FOR(i,1,n) {
		cin >> B[i];
		}
		sort(B+1,B+n+1);
		FOR(i,1,m){
			int x; cin >> x;
			int idx=lower_bound(B+1,B+n+1,x)-B;
			DEC(i,n,idx)B[i+1]=B[i];
			B[idx]=x;
			++n;
			int res=solve();
			if(res%2==0)cout<<res/2<<' ';
			else cout << res/2 << ".5 ";
		}
		
		exit(0);
	}
	seg=new node(0,m+3);
	int mx=0;
	int ans=0;
	FOR(i,1,m){
		cin >> A[i].f;
		A[i].s=i;
	}
	sort(A+1,A+m+1);
	FOR(i,1,m){
		where[A[i]]=i;
	}
	sort(A+1,A+m+1,[](pi x, pi y) {
		return x.s < y.s;
	});
	multiset<pi> ms;
	ms.insert(A[1]);
	cout << 0 << ' ';
	FOR(i,2,m) {
		auto it=ms.upper_bound(A[i]);
		if(it==ms.end()) {
			auto pre=prev(it);
			int nd=d - (A[i].f - pre->f);
			seg->update(where[*pre], nd);
		} else if(it==ms.begin()) {
			int nd=d- (it->f - A[i].f);
			seg->update(where[A[i]], nd);
		} else {
			auto pre=prev(it);
			int nd=d - (A[i].f - pre->f);
			seg->update(where[*pre], nd);
			
			nd=d-(it->f - A[i].f);
			seg->update(where[A[i]],nd);
		}
		
		ms.insert(A[i]);
		int ans=seg->get();
		if(ans%2==0)cout<<ans/2<<' ';
		else cout << ans/2 << ".5 ";
	}
}

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:124:6: warning: unused variable 'mx' [-Wunused-variable]
  124 |  int mx=0;
      |      ^~
Main.cpp:125:6: warning: unused variable 'ans' [-Wunused-variable]
  125 |  int ans=0;
      |      ^~~

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	356 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct

Subtask #2

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	356 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	44 ms	5068 KB	Output is correct
10	Correct	46 ms	5152 KB	Output is correct
11	Correct	33 ms	4356 KB	Output is correct
12	Correct	47 ms	4616 KB	Output is correct
13	Correct	26 ms	4240 KB	Output is correct
14	Correct	34 ms	4412 KB	Output is correct
15	Correct	37 ms	4296 KB	Output is correct
16	Correct	34 ms	4196 KB	Output is correct

Subtask #3

35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	243 ms	61816 KB	Output is correct
2	Correct	260 ms	63220 KB	Output is correct
3	Correct	255 ms	63192 KB	Output is correct
4	Correct	253 ms	60988 KB	Output is correct
5	Correct	251 ms	62484 KB	Output is correct
6	Correct	247 ms	61484 KB	Output is correct
7	Correct	250 ms	62404 KB	Output is correct
8	Correct	242 ms	61180 KB	Output is correct
9	Correct	260 ms	61088 KB	Output is correct
10	Correct	248 ms	63428 KB	Output is correct
11	Correct	243 ms	61888 KB	Output is correct
12	Correct	266 ms	62872 KB	Output is correct
13	Correct	254 ms	61064 KB	Output is correct
14	Correct	257 ms	62972 KB	Output is correct
15	Correct	255 ms	62912 KB	Output is correct
16	Correct	246 ms	61068 KB	Output is correct
17	Correct	258 ms	62468 KB	Output is correct

Subtask #4

41.0 / 41.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	243 ms	61816 KB	Output is correct
2	Correct	260 ms	63220 KB	Output is correct
3	Correct	255 ms	63192 KB	Output is correct
4	Correct	253 ms	60988 KB	Output is correct
5	Correct	251 ms	62484 KB	Output is correct
6	Correct	247 ms	61484 KB	Output is correct
7	Correct	250 ms	62404 KB	Output is correct
8	Correct	242 ms	61180 KB	Output is correct
9	Correct	260 ms	61088 KB	Output is correct
10	Correct	248 ms	63428 KB	Output is correct
11	Correct	243 ms	61888 KB	Output is correct
12	Correct	266 ms	62872 KB	Output is correct
13	Correct	254 ms	61064 KB	Output is correct
14	Correct	257 ms	62972 KB	Output is correct
15	Correct	255 ms	62912 KB	Output is correct
16	Correct	246 ms	61068 KB	Output is correct
17	Correct	258 ms	62468 KB	Output is correct
18	Correct	906 ms	61472 KB	Output is correct
19	Correct	890 ms	63940 KB	Output is correct
20	Correct	286 ms	64404 KB	Output is correct
21	Correct	376 ms	62200 KB	Output is correct
22	Correct	589 ms	62832 KB	Output is correct
23	Correct	361 ms	62364 KB	Output is correct
24	Correct	902 ms	62940 KB	Output is correct
25	Correct	250 ms	62332 KB	Output is correct
26	Correct	818 ms	61944 KB	Output is correct
27	Correct	850 ms	64048 KB	Output is correct
28	Correct	568 ms	62744 KB	Output is correct
29	Correct	702 ms	62468 KB	Output is correct
30	Correct	369 ms	61480 KB	Output is correct
31	Correct	356 ms	63820 KB	Output is correct
32	Correct	345 ms	62924 KB	Output is correct
33	Correct	866 ms	60756 KB	Output is correct
34	Correct	358 ms	62948 KB	Output is correct