oj.uz

Submission #1043957

# Submission time Handle Problem Language Result Execution time Memory
1043957 2024-08-05T05:15:47 Z 김은성(#11005) Measures (CEOI22_measures) C++17
35 / 100
 148 ms 24760 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Node{
	ll mx, mn, ret;
} tree[1<<19];
ll lazy[1<<19];
const ll INF = 0x3ffffffffffffffll;
int m, fen[1<<18];
void updatefen(int v){
	while(v <= m){
		fen[v]++;
		v += v&(-v);
	}
}
int psum(int v){
	int ans = 0;
	while(v>0){
		ans+=fen[v];
		v -= v&(-v);
	}
	return ans;
}
void init(int v, int l, int r){
	tree[v].mx = -INF;
	tree[v].mn = INF;
	tree[v].ret = 0;
	if(l==r)
		return;
	int mid = (l+r)/2;
	init(2*v,l , mid);
	init(2*v+1,mid+1, r);
}
void update(int v, int l, int r, int idx, ll val){
	if(lazy[v]){
		tree[v].mx += lazy[v];
		tree[v].mn += lazy[v];
		if(l!=r){
			lazy[2*v] += lazy[v];
			lazy[2*v+1] += lazy[v];
		}
		lazy[v] = 0;
	}
	if(l==r){
		tree[v].mx = tree[v].mn = val;
		tree[v].ret = 0;
		return;
	}
	int mid = (l+r)/2;
	if(idx <= mid)
		update(2*v, l, mid, idx, val);
	else
		update(2*v+1, mid+1, r, idx, val);
	tree[v].mx = max(tree[2*v].mx, tree[2*v+1].mx);
	tree[v].mn = min(tree[2*v].mn, tree[2*v+1].mn);
	tree[v].ret = max(max(tree[2*v].ret, tree[2*v+1].ret), tree[2*v+1].mx - tree[2*v].mn);
}
void addrange(int v, int l, int r, int s, int e, ll val){
	if(lazy[v]){
		tree[v].mx += lazy[v];
		tree[v].mn += lazy[v];
		if(l!=r){
			lazy[2*v] += lazy[v];
			lazy[2*v+1] += lazy[v];
		}
		lazy[v] = 0;
	}
	if(e<l || r<s)
		return;
	if(s<=l && r<=e){
		tree[v].mx += val;
		tree[v].mn += val;
		if(l != r){
			lazy[2*v] += val;
			lazy[2*v+1] += val;
		}
	}
	else{
		int mid = (l+r)/2;
		addrange(2*v, l, mid, s, e, val);
		addrange(2*v+1, mid+1, r, s, e, val);
		tree[v].mx = max(tree[2*v].mx, tree[2*v+1].mx);
		tree[v].mn = min(tree[2*v].mn, tree[2*v+1].mn);
		tree[v].ret = max(max(tree[2*v].ret, tree[2*v+1].ret), tree[2*v+1].mx - tree[2*v].mn);
	}
}
int main(){
	int n, D, i;
	ll val;
	scanf("%d %d", &n, &m);
	scanf("%d", &D);
	vector<pair<ll, int> > a;
	for(i=0; i<m; i++){
		scanf("%lld", &val);
		a.push_back(make_pair(val, i));
	}
	sort(a.begin(), a.end());
	vector<int> idx(m);
	for(i=0; i<m; i++){
		idx[a[i].second] = i;
	}
	init(1, 0, m-1);
	for(i=0; i<m; i++){
		update(1, 0, m-1, idx[i], -a[idx[i]].first + D * (ll)psum(i+1));
		//printf("idx[i]=%d val=%lld\n", idx[i], -a[idx[i]].first);
		addrange(1, 0, m-1, i+1, m-1, D);
		updatefen(i+1);
		ll res = tree[1].ret;
		//printf("tree[1].mn=%lld mx=%lld\n", tree[1].mn, tree[1].mx);
		if(res % 2==0)
			printf("%lld ", res/2);
		else
			printf("%lld.5 ", res/2);
	}
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:90:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:91:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |  scanf("%d", &D);
      |  ~~~~~^~~~~~~~~~
Main.cpp:94:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |   scanf("%lld", &val);
      |   ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4440 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 4440 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 88 ms 22720 KB Output is correct
2 Correct 89 ms 24600 KB Output is correct
3 Correct 90 ms 24504 KB Output is correct
4 Correct 90 ms 23220 KB Output is correct
5 Correct 89 ms 23732 KB Output is correct
6 Correct 94 ms 23608 KB Output is correct
7 Correct 90 ms 23736 KB Output is correct
8 Correct 95 ms 23228 KB Output is correct
9 Correct 85 ms 23224 KB Output is correct
10 Correct 90 ms 24760 KB Output is correct
11 Correct 86 ms 23224 KB Output is correct
12 Correct 93 ms 24212 KB Output is correct
13 Correct 89 ms 22436 KB Output is correct
14 Correct 113 ms 24384 KB Output is correct
15 Correct 94 ms 24760 KB Output is correct
16 Correct 87 ms 22708 KB Output is correct
17 Correct 87 ms 23844 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 22720 KB Output is correct
2 Correct 89 ms 24600 KB Output is correct
3 Correct 90 ms 24504 KB Output is correct
4 Correct 90 ms 23220 KB Output is correct
5 Correct 89 ms 23732 KB Output is correct
6 Correct 94 ms 23608 KB Output is correct
7 Correct 90 ms 23736 KB Output is correct
8 Correct 95 ms 23228 KB Output is correct
9 Correct 85 ms 23224 KB Output is correct
10 Correct 90 ms 24760 KB Output is correct
11 Correct 86 ms 23224 KB Output is correct
12 Correct 93 ms 24212 KB Output is correct
13 Correct 89 ms 22436 KB Output is correct
14 Correct 113 ms 24384 KB Output is correct
15 Correct 94 ms 24760 KB Output is correct
16 Correct 87 ms 22708 KB Output is correct
17 Correct 87 ms 23844 KB Output is correct
18 Incorrect 148 ms 23732 KB Output isn't correct
19 Halted 0 ms 0 KB -