Submission #1199907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199907		Boomyday	Garden (JOI23_garden)	C++20	0 / 100	654 ms	720 KiB

garden

//
// Created by adavy on 5/11/2025.
//
#include <bits/stdc++.h>

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
    set<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(){
    cin >> N >> M >> D;
    int mnans = D*D;

    set<int> pxvals, pyvals;
    vector<pair<int,int>> lines;
    vector<vector<int>> index(D); // indexed by y value
    for(int i=0;i<N;++i){
        int x, y; cin >> x >> y;
        pxvals.insert(x);
        pyvals.insert(y);
    }
    for (int i=0;i<M;++i){
        int x, y; cin >> x >> y;
        index[y].push_back(x);
    }

    for(auto&a:index){
        sort(a.begin(), a.end());
    }

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


        vector<vector<int>> events(D); // representing position of R
        for(int Y=0;Y<D;++Y){
            if (index[Y].size() == 0) continue;
            auto fval = lower_bound(index[Y].begin(), index[Y].end(), L);
            if (fval == index[Y].begin()) fval = index[Y].end();
            // subtract
            fval--;
            if (fval == index[Y].end()) continue;
            int x = *fval;

            events[x].push_back(Y);
        }
        // set up and mantain the sieve
        Sieve sieve;
        // add all the normal points
        for (auto&y:pyvals){
            sieve.insert(y);
        }
        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 (binary_search(pxvals.begin(), pxvals.end(), (R+1)%D)){
                    break;
                }
            }
            mnans = min(mnans, ((R-L+D)%D+1)*(D+1-sieve.get_max_gap()));
            // add events
            for(auto&y:events[R] ){
                sieve.insert(y);
            }


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

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