Submission #654333

#TimeUsernameProblemLanguageResultExecution timeMemory
654333sunwukong123Measures (CEOI22_measures)C++14
100 / 100
906 ms64404 KiB
#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 (stderr)

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;
      |      ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...