Submission #937823

#	Time	Username	Problem	Language	Result	Execution time	Memory
937823		anton	Garden (JOI23_garden)	C++17	30 / 100	3036 ms	19184 KiB

garden

#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int, int>
int n, m, d;

vector<pii> vecn;
vector<pii> vecm;


set<int> h_important;
set<int> w_important;
signed main(){
    cin>>n>>m>>d;

    for(int i = 0; i<n; i++){
        pii v;
        cin>>v.second>>v.first;
        vecn.push_back(v);
        h_important.insert(v.first);
        w_important.insert(v.second);
    }
    for(int i = 0; i<m; i++){
        pii v;
        cin>>v.second>>v.first;
        vecm.push_back(v);
        
        h_important.insert(v.first);
        w_important.insert(v.second);
    }

    sort(vecn.begin(), vecn.end());



    deque<int> vn;
    for(auto e: vecn){
        vn.push_back(e.first);
    }

    int res= 1e18;

    sort(vecm.begin(), vecm.end());
    deque<pii> vm;
    for(auto e: vecm){
        vm.push_back(e);
    }

    for(auto i: h_important){
        deque<int> hn;
        auto cmp = [&](pii&a, pii& b){
            return a.second<b.second;
        };
        sort(vecn.begin(), vecn.end(), cmp);
        for(auto e: vecn){
            hn.push_back(e.second);
        }

        for(auto j: w_important){
            //cout<<i<<" "<<j<<endl;
            
            int cvm =vm.size()-1;
            int h = max(vn.back(), vm[cvm].first);
            int w= hn.back();
            
            res= min(res, (h-i+1)*(w-j+1));
            
            while(cvm>0){
                pii last=vm[cvm];
                if(j>last.second){
                    last.second+=d;
                }
                cvm--;
                w= max(w, last.second);
                h= vn.back();
                if(cvm>0){
                    h =max(h, vm[cvm].first);
                }
                res= min(res, (h-i+1)*(w-j+1));
            }

            /*cout<<"vn"<<endl;
            for(auto e: vn){
                cout<<e<<" ";
            }
            cout<<endl;
            cout<<"hn"<<endl;
            for(auto e: hn){
                cout<<e<<" ";
            }
            cout<<endl;*/
            
            while(hn.size()>0 && hn.front()==j){
                int cur= hn.front();
                hn.pop_front();
                hn.push_back(cur+d);
            }
        }

        while(vn.size()>0 && vn.front()==i){
            int cur= vn.front();
            vn.pop_front();
            vn.push_back(cur+d);
        }
        while(vm.size()>0 && vm.front().first==i){
            pii cur= vm.front();
            vm.pop_front();
            vm.push_back({cur.first+d, cur.second});
        }
    }

    cout<<res<<endl;


}

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