Submission #1136767

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136767		Unforgettablepl	Room Temperature (JOI24_ho_t1)	C++20	100 / 100	882 ms	110028 KiB

Main

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

#define int long long

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,t;
    cin >> n >> t;
    vector<int> arr(n+1);
    vector<tuple<int,bool,int>> events;
    for(int i=1;i<=n;i++) {
        int a;cin>>a;
        a%=t;
        events.emplace_back(0,!true,+a);
        events.emplace_back(a,!false,+a);
        events.emplace_back(a,!true,-a);
        events.emplace_back(a+1+t/2,!false,-a);
        events.emplace_back(a+1+t/2,!true,+a+t);
        events.emplace_back(a+t,!false,+a+t);
        events.emplace_back(a+t,!true,-(a+t));
    }
    sort(events.begin(),events.end());
    int negCnt = 0;
    int posCnt = 0;
    multiset<int> negSum,posSum;
    int ans = 1e17;
    for(int i = 0;i<events.size();i++) {
        auto [position,typ,x] = events[i];
        if(!typ) {
            if(x>0) {
                posCnt++;
                posSum.insert(x);
            } else {
                negCnt++;
                negSum.insert(x);
            }
        } else {
            if(x>0) {
                posCnt--;
                posSum.erase(posSum.find(x));
            } else {
                negCnt--;
                negSum.erase(negSum.find(x));
            }
        }
        if(i==events.size()-1 or get<0>(events[i+1])!=position) {
            if(!negSum.empty() and !posSum.empty()) {
                int neg = *(--negSum.end());neg = -neg;
                int pos = *(--posSum.end());
                int newPosition = (neg+pos)/2;
                if(newPosition<position)newPosition=position;
                else if(i!=events.size()-1 and get<0>(events[i+1])<=newPosition)newPosition=get<0>(events[i+1])-1;
                position = newPosition;
            }
            int negMax = 0;
            if(!negSum.empty())negMax = position + *(--negSum.end());
            int posMax = 0;
            if(!posSum.empty())posMax = - position + *(--posSum.end());
            ans=min(ans,max(posMax,negMax));
        }
    }
    cout << ans << '\n';
}

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