Submission #1199933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199933		Boomyday	Garden (JOI23_garden)	C++20	45 / 100	3094 ms	2408 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());
    }
    */
    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(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 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 (binary_search(pxvals.begin(), pxvals.end(), (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: 6 / 6
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 0 / 30
• Subtask 6: 0 / 25