oj.uz

답안 #654333

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
654333 2022-10-31T02:56:10 Z sunwukong123 Measures (CEOI22_measures) C++14
100 / 100
 906 ms 64404 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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