Submission #1024953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024953		Alihan_8	Garden (JOI23_garden)	C++17	0 / 100	2003 ms	36076 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;

        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]);
            }
        }

        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];

            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]]);
            }
            
            if ( R_[j] == -1 && L_[j] != -1 ){
				chmax(maxDiff, d - a[L_[j]]);
			}
			
			if ( L_[j] == -1 && R_[j] != -1 ){
				chmax(maxDiff, a[R_[j]]);
			}
        };

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

            if ( r >= mx ){
                auto f__ = chmin(opt, (r - l + 1) * (d - maxDiff + 1));
            }
        }
    }

    cout << opt;

    cout << '\n';
}

Compilation message (stderr)

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

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