oj.uz

Submission #683166

# Submission time Handle Problem Language Result Execution time Memory
683166 2023-01-17T21:11:32 Z arnold518 Measures (CEOI22_measures) C++17
100 / 100
 314 ms 32212 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5+10;
const ll INF = 1e18;

int N, M, D;
pll A[MAXN+10];

struct SEG
{
	pll tree[MAXN*4+10];
	ll tree2[MAXN*4+10];
	ll lazy[MAXN*4+10];
	SEG()
	{
		fill(tree, tree+MAXN*4+10, pll(-INF, INF));
		fill(tree2, tree2+MAXN*4+10, -INF);
	}
	void busy(int node, int tl, int tr)
	{
		if(!lazy[node]) return;
		tree[node].first+=lazy[node]; tree[node].second+=lazy[node];
		if(tl!=tr)
		{
			lazy[node*2]+=lazy[node];
			lazy[node*2+1]+=lazy[node];
		}
		lazy[node]=0;
	}
	void update(int node, int tl, int tr, int l, int r, ll k, bool n)
	{
		busy(node, tl, tr);
		if(r<tl || tr<l) return;
		if(l<=tl && tr<=r)
		{
			if(n)
			{
				tree[node].first+=INF;
				tree[node].second-=INF;
				tree2[node]=0;
			}
			lazy[node]+=k;
			busy(node, tl, tr);
			return;
		}
		int mid=tl+tr>>1;
		update(node*2, tl, mid, l, r, k, n);
		update(node*2+1, mid+1, tr, l, r, k, n);
		tree[node].first=max(tree[node*2].first, tree[node*2+1].first);
		tree[node].second=min(tree[node*2].second, tree[node*2+1].second);
		tree2[node]=max({tree2[node*2], tree2[node*2+1], tree[node*2].first-tree[node*2+1].second});
	}
	ll query()
	{
		return tree2[1];
	}
}seg;

int pos[MAXN+10];

int main()
{
	scanf("%d%d%d", &N, &M, &D);
	for(int i=1; i<=N; i++) scanf("%lld", &A[i].first), A[i].second=i;
	for(int i=1; i<=M; i++) scanf("%lld", &A[N+i].first), A[N+i].second=N+i;
	M+=N;
	sort(A+1, A+M+1);
	for(int i=1; i<=M; i++) pos[A[i].second]=i;

	for(int i=1; i<=M; i++)
	{
		seg.update(1, 1, M, pos[i], M, -D, 0);
		seg.update(1, 1, M, pos[i], pos[i], A[pos[i]].first, 1);
		if(i>N)
		{
			ll t=seg.query();
			if(t%2==0) printf("%lld ", t/2);
			else printf("%lld.5 ", t/2);
		}
	}

}

Compilation message

Main.cpp: In member function 'void SEG::update(int, int, int, int, int, ll, bool)':
Main.cpp:51:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |   int mid=tl+tr>>1;
      |           ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |  scanf("%d%d%d", &N, &M, &D);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:69:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |  for(int i=1; i<=N; i++) scanf("%lld", &A[i].first), A[i].second=i;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~
Main.cpp:70:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |  for(int i=1; i<=M; i++) scanf("%lld", &A[N+i].first), A[N+i].second=N+i;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19156 KB Output is correct
2 Correct 11 ms 19108 KB Output is correct
3 Correct 11 ms 19116 KB Output is correct
4 Correct 11 ms 19156 KB Output is correct
5 Correct 10 ms 19156 KB Output is correct
6 Correct 11 ms 19116 KB Output is correct
7 Correct 11 ms 19156 KB Output is correct
8 Correct 10 ms 19156 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19156 KB Output is correct
2 Correct 11 ms 19108 KB Output is correct
3 Correct 11 ms 19116 KB Output is correct
4 Correct 11 ms 19156 KB Output is correct
5 Correct 10 ms 19156 KB Output is correct
6 Correct 11 ms 19116 KB Output is correct
7 Correct 11 ms 19156 KB Output is correct
8 Correct 10 ms 19156 KB Output is correct
9 Correct 244 ms 29008 KB Output is correct
10 Correct 228 ms 29024 KB Output is correct
11 Correct 136 ms 28984 KB Output is correct
12 Correct 172 ms 29004 KB Output is correct
13 Correct 131 ms 28528 KB Output is correct
14 Correct 150 ms 28940 KB Output is correct
15 Correct 241 ms 28428 KB Output is correct
16 Correct 130 ms 28996 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 30088 KB Output is correct
2 Correct 170 ms 31936 KB Output is correct
3 Correct 156 ms 31976 KB Output is correct
4 Correct 153 ms 29772 KB Output is correct
5 Correct 154 ms 31176 KB Output is correct
6 Correct 152 ms 30156 KB Output is correct
7 Correct 157 ms 31056 KB Output is correct
8 Correct 155 ms 29812 KB Output is correct
9 Correct 194 ms 29776 KB Output is correct
10 Correct 159 ms 32212 KB Output is correct
11 Correct 157 ms 30588 KB Output is correct
12 Correct 158 ms 31532 KB Output is correct
13 Correct 148 ms 29724 KB Output is correct
14 Correct 182 ms 31764 KB Output is correct
15 Correct 157 ms 31556 KB Output is correct
16 Correct 150 ms 29376 KB Output is correct
17 Correct 171 ms 31072 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 30088 KB Output is correct
2 Correct 170 ms 31936 KB Output is correct
3 Correct 156 ms 31976 KB Output is correct
4 Correct 153 ms 29772 KB Output is correct
5 Correct 154 ms 31176 KB Output is correct
6 Correct 152 ms 30156 KB Output is correct
7 Correct 157 ms 31056 KB Output is correct
8 Correct 155 ms 29812 KB Output is correct
9 Correct 194 ms 29776 KB Output is correct
10 Correct 159 ms 32212 KB Output is correct
11 Correct 157 ms 30588 KB Output is correct
12 Correct 158 ms 31532 KB Output is correct
13 Correct 148 ms 29724 KB Output is correct
14 Correct 182 ms 31764 KB Output is correct
15 Correct 157 ms 31556 KB Output is correct
16 Correct 150 ms 29376 KB Output is correct
17 Correct 171 ms 31072 KB Output is correct
18 Correct 253 ms 30280 KB Output is correct
19 Correct 301 ms 32040 KB Output is correct
20 Correct 155 ms 31932 KB Output is correct
21 Correct 180 ms 29916 KB Output is correct
22 Correct 262 ms 30272 KB Output is correct
23 Correct 165 ms 30064 KB Output is correct
24 Correct 259 ms 30544 KB Output is correct
25 Correct 160 ms 29764 KB Output is correct
26 Correct 250 ms 29704 KB Output is correct
27 Correct 314 ms 32172 KB Output is correct
28 Correct 220 ms 30188 KB Output is correct
29 Correct 231 ms 31516 KB Output is correct
30 Correct 190 ms 29772 KB Output is correct
31 Correct 193 ms 31672 KB Output is correct
32 Correct 179 ms 31592 KB Output is correct
33 Correct 247 ms 29340 KB Output is correct
34 Correct 182 ms 31052 KB Output is correct