oj.uz

Submission #968585

# Submission time Handle Problem Language Result Execution time Memory
968585 2024-04-23T16:15:59 Z marvinthang Measures (CEOI22_measures) C++17
100 / 100
 126 ms 32964 KB 
/*************************************
*    author: marvinthang             *
*    created: 23.04.2024 22:44:57    *
*************************************/

#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i-- > 0; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }

// end of template

const long long INF = 1e18;

int n, m, d;

struct Node {
	long long res, min_val, max_val;
	int cnt;
	Node(): res(0), min_val(INF), max_val(-INF), cnt(0) {}
	Node(long long val): res(0), min_val(val), max_val(val), cnt(1) {}
	Node operator + (const Node &ot) const {
		Node ans;
		ans.res = max({res, ot.res, ot.max_val + 1LL * cnt * d - min_val});
		ans.min_val = min(min_val, ot.min_val + 1LL * cnt * d);
		ans.max_val = max(max_val, ot.max_val + 1LL * cnt * d);
		ans.cnt = cnt + ot.cnt;
		return ans;
	}
};

void process(void) {
	cin >> n >> m >> d;
	m += n;
	vector <int> a(m); cin >> a;
	vector <int> order(m);
	iota(ALL(order), 0);
	sort(ALL(order), [&] (int i, int j) { return a[i] < a[j]; });
	vector <int> pos(m);
	REP(i, m) pos[order[i]] = i;
	vector <Node> st(m * 4 + 23);
	auto update = [&] (auto &&self, int i, int l, int r, int p, int v) -> void {
		if (r - l == 1) {
			st[i] = Node(-v);
			return;
		}
		int m = (l + r) / 2;
		if (p < m) self(self, i << 1, l, m, p, v);
		else self(self, i << 1 | 1, m, r, p, v);
		st[i] = st[i << 1] + st[i << 1 | 1];
	};
	REP(i, m) {
		update(update, 1, 0, m, pos[i], a[i]);
		if (i >= n) cout << st[1].res / 2 << (st[1].res & 1 ? ".5" : "") << ' ';
	}
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
	file("measures");
	// int t; cin >> t; while (t--)
	process();
	// cerr << "Time elapsed: " << TIME << " s.\n";
	return (0^0);
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:30:61: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:92:2: note: in expansion of macro 'file'
   92 |  file("measures");
      |  ^~~~
Main.cpp:30:94: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:92:2: note: in expansion of macro 'file'
   92 |  file("measures");
      |  ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 600 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 109 ms 27852 KB Output is correct
10 Correct 89 ms 27628 KB Output is correct
11 Correct 54 ms 27736 KB Output is correct
12 Correct 79 ms 27616 KB Output is correct
13 Correct 49 ms 27732 KB Output is correct
14 Correct 57 ms 27736 KB Output is correct
15 Correct 105 ms 27888 KB Output is correct
16 Correct 52 ms 27728 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 28708 KB Output is correct
2 Correct 74 ms 32596 KB Output is correct
3 Correct 91 ms 32700 KB Output is correct
4 Correct 66 ms 30544 KB Output is correct
5 Correct 70 ms 31828 KB Output is correct
6 Correct 67 ms 30928 KB Output is correct
7 Correct 69 ms 31796 KB Output is correct
8 Correct 67 ms 30540 KB Output is correct
9 Correct 65 ms 30540 KB Output is correct
10 Correct 86 ms 32964 KB Output is correct
11 Correct 67 ms 31316 KB Output is correct
12 Correct 74 ms 32156 KB Output is correct
13 Correct 67 ms 30540 KB Output is correct
14 Correct 75 ms 32592 KB Output is correct
15 Correct 72 ms 32320 KB Output is correct
16 Correct 65 ms 30036 KB Output is correct
17 Correct 70 ms 31760 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 28708 KB Output is correct
2 Correct 74 ms 32596 KB Output is correct
3 Correct 91 ms 32700 KB Output is correct
4 Correct 66 ms 30544 KB Output is correct
5 Correct 70 ms 31828 KB Output is correct
6 Correct 67 ms 30928 KB Output is correct
7 Correct 69 ms 31796 KB Output is correct
8 Correct 67 ms 30540 KB Output is correct
9 Correct 65 ms 30540 KB Output is correct
10 Correct 86 ms 32964 KB Output is correct
11 Correct 67 ms 31316 KB Output is correct
12 Correct 74 ms 32156 KB Output is correct
13 Correct 67 ms 30540 KB Output is correct
14 Correct 75 ms 32592 KB Output is correct
15 Correct 72 ms 32320 KB Output is correct
16 Correct 65 ms 30036 KB Output is correct
17 Correct 70 ms 31760 KB Output is correct
18 Correct 114 ms 30804 KB Output is correct
19 Correct 116 ms 32520 KB Output is correct
20 Correct 78 ms 32852 KB Output is correct
21 Correct 98 ms 30652 KB Output is correct
22 Correct 94 ms 31060 KB Output is correct
23 Correct 75 ms 30836 KB Output is correct
24 Correct 123 ms 31400 KB Output is correct
25 Correct 68 ms 30548 KB Output is correct
26 Correct 112 ms 30320 KB Output is correct
27 Correct 126 ms 32848 KB Output is correct
28 Correct 91 ms 30848 KB Output is correct
29 Correct 98 ms 32332 KB Output is correct
30 Correct 96 ms 30452 KB Output is correct
31 Correct 100 ms 32372 KB Output is correct
32 Correct 77 ms 32204 KB Output is correct
33 Correct 108 ms 30140 KB Output is correct
34 Correct 99 ms 31824 KB Output is correct