Submission #1199936

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199936		Boomyday	Garden (JOI23_garden)	C++20	15 / 100	2308 ms	590616 KiB

garden

//
// Created by adavy on 5/11/2025.
//
#include <bits/stdc++.h>
// add o3
#pragma GCC optimize("O3")
using namespace std;

using ll = long long;
int N, M, D;

struct Sieve{
    set<int> vals;
    // a circular set, from 0 to D, maintain the maximum gap in the sieve
    multiset<int, greater<int>> gaps;
    void insert(int x){

        if (vals.find(x) != vals.end()) return;
        if (vals.size() == 0){
            vals.insert(x);
            return;
        }
        // get index of left and right neighbours
        auto right_it = vals.lower_bound(x);
        if (right_it == vals.end()){
            right_it = vals.begin();
        }
        int right_nei = *right_it;
        auto left_it = right_it;
        if (left_it == vals.begin()){
            left_it = vals.end();
        }
        left_it--;
        int left_nei = *left_it;
        if (left_nei != right_nei){
            gaps.erase(gaps.find((right_nei - left_nei + D)%D));
        }
        gaps.insert((x - left_nei + D)%D);
        gaps.insert((right_nei - x + D)%D);
        vals.insert(x);
    }

    int get_max_gap(){
        if (gaps.size() <= 1) return D;
        return *gaps.begin();
    } // beware of off by one error


};


int main(){
    //freopen("input.txt", "r", stdin);
    //std::ios::sync_with_stdio(false);
    //cin.tie(NULL);
    cin >> N >> M >> D;
    int mnans = D*D;



    set<int> spxvals, spyvals;
    vector<pair<int,int>> lines;
    vector<set<int>> sindex(D); // indexed by y value
    for(int i=0;i<N;++i){
        int x, y; cin >> x >> y;
        spxvals.insert(x);
        spyvals.insert(y);
    }
    for (int i=0;i<M;++i){
        int x, y; cin >> x >> y;
        sindex[y].insert(x);
    }
    vector<vector<int>> index(D);
    for (int i=0;i<D;++i){
        index[i] = vector<int>(sindex[i].begin(), sindex[i].end());
    }
    vector<int> pxvals(spxvals.begin(), spxvals.end());
    vector<int> pyvals(spyvals.begin(), spyvals.end());
    /*
    for(auto&a:index){
        sort(a.begin(), a.end());
    }
    */

    vector<vector<vector<int>>> all_events(D);  // all_events[L][R] = vector of Y to insert

// Initialize to empty events for each L
    for (int L = 0; L < D; ++L)
        all_events[L] = vector<vector<int>>(D);  // size D for R positions

    for (int y = 0; y < D; ++y) {
        const auto& xs = index[y];
        if (xs.empty()) continue;

        int sz = xs.size();
        for (int i = 0; i < sz; ++i) {
            int x = xs[i];
            // This x is the largest less than L in [0, D) if L == xs[i+1]
            // We want it to be used for L in (xs[i], xs[i+1]]
            int L_begin = (x + 1) % D;
            int L_end = (i + 1 < sz ? xs[i + 1] : xs[0] + D) % D;

            // Assign y to all L in range [L_begin, L_end) mod D
            for (int L = L_begin; L != L_end; L = (L + 1) % D) {
                all_events[L][x].push_back(y);
            }
        }
    }
    vector<bool> haspx(D, false);
    for (int x : pxvals) haspx[x] = true;

    Sieve sieve;
    // add all the normal points
    for (auto&y:pyvals){
        sieve.insert(y);
    }

    for(int L=0;L<D;++L){
        //cout << L << endl;


        vector<vector<int>> events = all_events[L];
        // set up and mantain the sieve
        Sieve sieve2(sieve);

        for (int R=(L-1+D)%D;;--R, R+=D, R%=D){

            // condition to break if a normal point is missed out w.r.t. x axis
            if (R!=(L-1+D)%D){
                // if (R+1)%D is in pxvals, break
                if (haspx[(R + 1) % D]) break;
            }
            //cout << "smg " << sieve.get_max_gap() << endl;

            //cout << L << " " << R << " " << ((R-L+D)%D+1) << " " << (D+1-sieve.get_max_gap()) << endl;
            mnans = min(mnans, ((R-L+D)%D+1)*(D+1-sieve2.get_max_gap()));
            // add events
            for(auto&y:events[R] ){
                sieve2.insert(y);
            }


            if (R==L) break;
        }
    }
    cout << mnans;
}

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