Submission #1182774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182774		Dedibeat	Room Temperature (JOI24_ho_t1)	C++20	85 / 100	2095 ms	53112 KiB

Main

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

#define F first
#define S second 
#define all(x) (x).begin(), (x).end()

template<typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p)
{
    return os << "(" << p.F << "," << p.S << ")";
}
template<typename T>
void print(const T &v, int lim = 1e9)
{
    for(auto x : v) 
        if(lim-- > 0) cout << x << " ";
    cout << "\n";
}

const int mxN = 5000005;
tuple<ll, int, int> stk[3 * mxN];
int rg[mxN];
ll a[mxN];
int tp = 0;
void stk_push(ll f, int s, int t)
{
    stk[tp] = {f, s, t};
    tp++;
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(NULL);
    int N, T;
    cin >> N >> T;
    for(int i = 0; i < N; i++)
    {
        cin >> a[i];
    }

    int l = -1, r = 1e9;
    while(l + 1 < r)
    {
        int mid = (l + r) / 2;
        tp = 0;
        int cnt = 0, mx = 0;
        for(int i = 0; i < N; i++)
        {
            ll y1 = a[i] % T, y2 = a[i] % T + T, y3 = a[i] % T - T;
            stk_push(y1 - mid,  0, i);
            stk_push(y1 + mid,  1, i);
            stk_push(y2 - mid,  0, i);
            stk_push(y2 + mid,  1, i);
            stk_push(y3 - mid,  0, i);
            stk_push(y3 + mid,  1, i);
        }

        sort(stk, stk + tp);
        for(int i = 0; i < tp; i++)
        {
            auto &[_, flg, idx] = stk[i];
            if(flg == 0)
            {
                if(rg[idx] == 0) cnt++;
                rg[idx]++;
            }
            else 
            {
                if(rg[idx] == 1) cnt--;
                rg[idx]--;
            }
            mx = max(cnt, mx);
        }

        if(mx == N) r = mid;
        else l = mid;
    }

    cout << r << "\n";




}

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