Submission #1031763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031763		Alihan_8	Garden (JOI23_garden)	C++17	45 / 100	3101 ms	24660 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]];
        }
    }
    
    if ( m <= 8 ){ // subtask #1
		vector <int> v(d * 2, -1), has(d * 2), tv(d * 2, -1);
		
		vector <vector<int>> er(d * 2);
		
		for ( int i = 0; i < n; i++ ){
			tv[Q[i]] = true;
			
			has[Q[i]] = true;
		}
		
		for ( int i = 0; i < m; i++ ){
			chmax(v[S[i]], R[i]);
			
			has[S[i]] = true;
		}
		
		for ( int i = 0; i < d * 2; i++ ){
			if ( v[i] != -1 ){
				er[v[i]].pb(i);
			}
		}
	 
		int opt = 1e9, mx = *max_element(all(P)), _ip = 0, _ir = 0;
	 
		for ( int l = 0; l < d; l++ ){
			while ( _ip < n && P[_ip] < l ){
				chmax(mx, P[_ip] + d);
	 
				_ip++;
			}
			
			while ( _ir < m && R[_ir] < l ){
				auto flag = chmax(v[S[_ir]], R[_ir] + d);
				
				if ( flag > 0 ){
					er[R[_ir] + d].pb(S[_ir]);
				}
				
				_ir++;
			}
			
			set <int> st;
			
			vector <int> lf(d * 2, -1), rg(d * 2, -1);
			
			for ( int i = 1; i < d * 2; i++ ){
				if ( has[i - 1] > 0 ){
					lf[i] = i - 1;
				} else{
					lf[i] = lf[i - 1];
				}
			}
			
			for ( int i = (d - 1) * 2; i >= 0; i-- ){
				if ( has[i + 1] ){
					rg[i] = i + 1;
				} else{
					rg[i] = rg[i + 1];
				}
			}
			
			int maxDiff = 0;
			
			for ( int i = 0; i < d * 2; i++ ){
				if ( has[i] > 0 ){
					st.insert(i);
					
					if ( rg[i] != -1 ){
						chmax(maxDiff, rg[i] - i);
					}
				}
			}
			
			auto del = [&](int x){
				st.erase(x);
				
				if ( lf[x] != -1 ){
					rg[lf[x]] = rg[x];
				}
				if ( rg[x] != -1 ){
					lf[rg[x]] = lf[x];
				}
				
				if ( lf[x] != -1 && rg[x] != -1 ){
					chmax(maxDiff, rg[x] - lf[x]);
				}
			};	
			
			for ( int r = l; r <= l + d; r++ ){
				for ( auto &y: er[r] ){
					if ( tv[y] < 1 ){
						del(y);
					}
				}
				
				if ( r >= mx ){
					chmin(opt, (r - l + 1) * min(*st.rbegin() - *st.begin() + 1, d - maxDiff + 1));
					
					/*cout << l << " " << r << " -> " << opt << " maxDiff : " << maxDiff << ln;
					for ( auto &u: st ) cout << u << ' ';
					cout << ln;
					opt = 1e9;*/
					
				}
			}
		}
	 
		cout << opt << ln;
		
		return 0;
	}
	
	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 : 
2 2 5
4 0
1 1
0 0
2 2

Expected 
8
Your out : 
4

*/

Compilation message (stderr)

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

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