Submission #1083403

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083403		quangminh412	Room Temperature (JOI24_ho_t1)	C++14	100 / 100	206 ms	71796 KiB

Main

#include <bits/stdc++.h>
using namespace std;

/*
  John Watson
  https://codeforces.com/profile/quangminh98

  Mua Code nhu mua Florentino !!
*/

#define faster() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long

const int maxn = 5e5 + 9;
const int segsize = 8 * maxn;
const ll oo = 1e18;

int n, t;
ll arr[maxn];

class SegmentTree
{
private:	
	struct Node
	{
		ll mn, mx;
		
		Node(ll mn = 1e18, ll mx = -1e18) : mn(mn), mx(mx) {}
		
		Node operator + (const Node& other)
		{
			Node res;
			res.mn = min(mn, other.mn);
			res.mx = max(mx, other.mx);
			return res;
		}
	};	
	
	vector<Node> st;
	int n;
	
	void build(int head, int l, int r, ll *arr, int t)
	{
		if (l == r)
		{
			int idx = (l % n == 0 ? n : l % n);
			int can = (l > n);
			st[head] = Node(arr[idx] + can * t, arr[idx] + can * t);
			return;
		}
		
		int mid = l + r >> 1;
		build(2 * head, l, mid, arr, t);
		build(2 * head + 1, mid + 1, r, arr, t);
		
		st[head] = st[2 * head] + st[2 * head + 1];
	}
	
	Node query(int head, int l, int r, int u, int v)
	{
		if (l > v || r < u) return Node();
		if (u <= l && r <= v) return st[head];
		
		int mid = l + r >> 1;
		return query(2 * head, l, mid, u, v) + query(2 * head + 1, mid + 1, r, u, v);
	}
public:
	SegmentTree(int n, ll *arr, int t) : n(n) 
	{ 
		st.resize(segsize); 
		build(1, 1, 2 * n, arr, t); 
	}
	
	pair<ll, ll> query(int u, int v) // min, max
	{
		Node ans = query(1, 1, 2 * n, u, v);
		return {ans.mn, ans.mx};
	}
};

signed main()
{
	if (fopen("test.inp", "r"))
	{
		freopen("test.inp", "r", stdin);
		freopen("test.out", "w", stdout);
	}
	faster();

	cin >> n >> t;
	for (int i = 1; i <= n; i++)
	{
		cin >> arr[i];
		arr[i] %= t;
	}
	sort(arr + 1, arr + n + 1);
	SegmentTree seg(n, arr, t);
		
	ll res = oo;
	for (int i = 1; i <= n + 1; i++)
	{
		pair<ll, ll> val = seg.query(i, i + n - 1);
		ll mid = (val.first + val.second) / 2;
		res = min(res, max(mid - val.first, val.second - mid));
	}
		
	cout << res << '\n';
		
	return 0;
}

Compilation message (stderr)

Main.cpp: In member function 'void SegmentTree::build(int, int, int, long long int*, int)':
Main.cpp:52:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |   int mid = l + r >> 1;
      |             ~~^~~
Main.cpp: In member function 'SegmentTree::Node SegmentTree::query(int, int, int, int, int)':
Main.cpp:64:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |   int mid = l + r >> 1;
      |             ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:85:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |   freopen("test.inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:86:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |   freopen("test.out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 35 / 35
• Subtask 5: 15 / 15