oj.uz

Submission #654330

# Submission time Handle Problem Language Result Execution time Memory
654330 2022-10-31T02:54:09 Z sunwukong123 Measures (CEOI22_measures) C++14
76 / 100
 901 ms 64408 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;

int32_t main() 
{
	IAMSPEED
	cin >> n >> m >> d;
	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:90:6: warning: unused variable 'mx' [-Wunused-variable]
   90 |  int mx=0;
      |      ^~
Main.cpp:91:6: warning: unused variable 'ans' [-Wunused-variable]
   91 |  int ans=0;
      |      ^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 61400 KB Output is correct
2 Correct 291 ms 64156 KB Output is correct
3 Correct 265 ms 63852 KB Output is correct
4 Correct 261 ms 61336 KB Output is correct
5 Correct 250 ms 63376 KB Output is correct
6 Correct 272 ms 62080 KB Output is correct
7 Correct 273 ms 63424 KB Output is correct
8 Correct 257 ms 62392 KB Output is correct
9 Correct 246 ms 61956 KB Output is correct
10 Correct 258 ms 64244 KB Output is correct
11 Correct 258 ms 62516 KB Output is correct
12 Correct 248 ms 63624 KB Output is correct
13 Correct 254 ms 61648 KB Output is correct
14 Correct 246 ms 63860 KB Output is correct
15 Correct 256 ms 63504 KB Output is correct
16 Correct 245 ms 61832 KB Output is correct
17 Correct 254 ms 63348 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 61400 KB Output is correct
2 Correct 291 ms 64156 KB Output is correct
3 Correct 265 ms 63852 KB Output is correct
4 Correct 261 ms 61336 KB Output is correct
5 Correct 250 ms 63376 KB Output is correct
6 Correct 272 ms 62080 KB Output is correct
7 Correct 273 ms 63424 KB Output is correct
8 Correct 257 ms 62392 KB Output is correct
9 Correct 246 ms 61956 KB Output is correct
10 Correct 258 ms 64244 KB Output is correct
11 Correct 258 ms 62516 KB Output is correct
12 Correct 248 ms 63624 KB Output is correct
13 Correct 254 ms 61648 KB Output is correct
14 Correct 246 ms 63860 KB Output is correct
15 Correct 256 ms 63504 KB Output is correct
16 Correct 245 ms 61832 KB Output is correct
17 Correct 254 ms 63348 KB Output is correct
18 Correct 804 ms 62752 KB Output is correct
19 Correct 847 ms 63948 KB Output is correct
20 Correct 275 ms 64408 KB Output is correct
21 Correct 370 ms 62304 KB Output is correct
22 Correct 573 ms 62628 KB Output is correct
23 Correct 364 ms 62476 KB Output is correct
24 Correct 901 ms 62832 KB Output is correct
25 Correct 274 ms 62376 KB Output is correct
26 Correct 891 ms 62140 KB Output is correct
27 Correct 898 ms 64028 KB Output is correct
28 Correct 573 ms 62752 KB Output is correct
29 Correct 720 ms 62688 KB Output is correct
30 Correct 355 ms 61472 KB Output is correct
31 Correct 386 ms 63816 KB Output is correct
32 Correct 338 ms 62980 KB Output is correct
33 Correct 849 ms 60700 KB Output is correct
34 Correct 351 ms 63024 KB Output is correct