Submission #1025035

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025035		Alihan_8	Garden (JOI23_garden)	C++17	30 / 100	3098 ms	55772 KiB

garden

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, d; cin >> n >> m >> d;

    vector <int> P(n), Q(n), R(m), S(m);

    for ( int i = 0; i < n; i++ ){
        cin >> P[i] >> Q[i];
    }

    for ( int i = 0; i < m; i++ ){
        cin >> R[i] >> S[i];
    }

    { // sorting
        vector <int> p_(m);

        iota(all(p_), 0);

        sort(all(p_), [&](int &u, int &v){
             return R[u] < R[v];
        });

        auto _R = R, _S = S;

        for ( int i = 0; i < m; i++ ){
            R[i] = _R[p_[i]];
            S[i] = _S[p_[i]];
        }

        p_ = vector <int> (n);

        iota(all(p_), 0);

        sort(all(p_), [&](int &u, int &v){
             return P[u] < P[v];
        });

        auto _P = P, _Q = Q;

        for ( int i = 0; i < n; i++ ){
            P[i] = _P[p_[i]];
            Q[i] = _Q[p_[i]];
        }
    }

    vector <ar<int,2>> srt;

    auto a = Q;

    for ( int i = 0; i < n; i++ ){
        srt.pb({Q[i], -1});
    }

    for ( int i = 0; i < m; i++ ){
        srt.pb({S[i], i});

        a.pb(S[i]);
    }

    sort(all(a));

    sort(all(srt));

    vector <int> p(m);

    for ( int i = 0; i < n + m; i++ ){
        auto [val, j] = srt[i];

        if ( j != -1 ) p[j] = i;
    }

    vector <vector<int>> er_(d * 2);

    int opt = 1e9, mx = *max_element(all(P)), _ip = 0;

    for ( int l = 0; l < d; l++ ){
        while ( _ip < n && P[_ip] < l ){
            chmax(mx, P[_ip] + d);

            _ip++;
        }

        auto ok = [&](int x){ return x >= 0 && x < n + m; };

        int maxDiff = 0;
        
        multiset <int> st;

        vector <int> L_(n + m), R_(n + m);
		
        for ( int i = 0; i < n + m; i++ ){
            L_[i] = i - 1; R_[i] = i + 1;

            if ( ok(L_[i]) ){
                chmax(maxDiff, a[i] - a[L_[i]]);
            } 
			

            if ( ok(R_[i]) ){
                chmax(maxDiff, a[R_[i]] - a[i]);
            } 
            
            st.insert(a[i]);
        }

        for ( int i = 0; i < m; i++ ){
            int v = (R[i] < l ? R[i] + d : R[i]);

            er_[v].pb(i);
        }
        
        auto er = [&](int j){
            j = p[j];
            
            st.erase(st.find(a[j]));

            if ( ok(R_[j]) ){
                L_[R_[j]] = L_[j];
            } 

            if ( ok(L_[j]) ){
                R_[L_[j]] = R_[j];
            } 

            if ( ok(L_[j]) && ok(R_[j]) ){
                chmax(maxDiff, a[R_[j]] - a[L_[j]]);
            }
		};

        for ( int r = l; r <= l + d; r++ ){
            for ( auto &j: er_[r] ){
                er(j);
            } er_[r].clear();

            if ( r >= mx ){
                auto tmp = chmin(opt, (r - l + 1) * (min(*st.rbegin() - *st.begin() + 1, d - maxDiff + 1)));
            
				/*if ( tmp > 0 ){
					cout << l << " " << r << " -> " << opt << " cur len : " << *st.rbegin() - *st.begin() + 1 << " maxDiff : " << maxDiff << ln;
					for ( auto &u: st ) cout << u << ' '; cout << ln;
				}*/
            }
        }
    }

    cout << opt;

    cout << '\n';
}

/*
 
Wrong Answer on Test : 
3 2 4
3 3
0 1
0 3
0 0
0 0

Expected 
12
Your out : 
6



  
*/

Compilation message (stderr)

garden.cpp: In function 'int main()':
garden.cpp:169:22: warning: unused variable 'tmp' [-Wunused-variable]
  169 |                 auto tmp = chmin(opt, (r - l + 1) * (min(*st.rbegin() - *st.begin() + 1, d - maxDiff + 1)));
      |                      ^~~

• Subtask 1: 0 / 15
• Subtask 2: 6 / 6
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 0 / 30
• Subtask 6: 0 / 25