Submission #1144986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144986		Noproblem29	Garden (JOI23_garden)	C++20	100 / 100	435 ms	17212 KiB

garden

#include<bits/stdc++.h>
using namespace std;
#ifndef BADGNU
#pragma GCC target("sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#endif
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
#define ll long long
#define int ll
#define ld long double
#define y1 cheza
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class T> using ordered_multiset = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;
const int N=5e5+100;
const int M=5001;
const int B=447;
const int mod=998244353;
const ll INF=1e18;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
const double eps=1e-6;
struct consec{
    int sz,mx;
    vector<bool> mark;
    vector<int>pl,pr;
    consec(int x):sz(x),mx(0),mark(x),pl(x),pr(x){};
    void upd(int x){
        mark[x]=1;
        int tl=(x?x-1:sz-1);
        int tr=(x+1<sz?x+1:0);
        int l=(mark[tl]?pl[tl]:x);
        int r=(mark[tr]?pr[tr]:x);
        if(sz==1||tr==l){
            mx=sz;
            return;
        }
        mx=max(mx,(r-l+sz)%sz+1);
        pr[l]=r;
        pl[r]=l;
    } 
};
int n,m,d;
bool markx[M*2],marky[M*2];
vector<int>g[M*2],f[M*2];
int last[M];

void test(){
    cin>>n>>m>>d;
    for(int i=1,x,y;i<=n;i++){
        cin>>x>>y;
        markx[x]=1;
        markx[x+d]=1;
        marky[y]=1;
    }
    for(int i=1,x,y;i<=m;i++){
        cin>>x>>y;
        if(markx[x]||marky[y])continue;
        g[x].push_back(y);
        g[x+d].push_back(y);
    }
    int ans=d*d;
    for(int lx=1;lx<=d;lx++){
        if(!markx[lx-1])continue;
        int rx=lx;
        while(!markx[rx])rx++;
        for(int j=0;j<d;j++){
            last[j]=-1;
        }
        for(int l=rx;l>=lx;l--){
            if(l<rx){
                for(auto i:g[l])last[i]=l;
            }
            for(int i=l;i<rx;i++){
                f[i].clear();
            }

            consec scan(d);
            for(int i=0;i<d;i++){
                if(last[i]!=-1){
                    f[last[i]].push_back(i);
                }
                if(!marky[i]&&last[i]==-1){
                    scan.upd(i);
                }
            }
            for(int r=rx;r>=l;r--){
                if(r<rx){
                    for(auto i:f[r])scan.upd(i);    
                }
                ans=min(ans,(d-(r-l))*(d-scan.mx));
            }
        }
        lx=rx;
    }
    cout<<ans<<'\n';



    // 0 0 5
    // 1 2
    // 1 5
    // 2 5

}



/*

*/
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    // cout.tie(nullptr);
    int t2=1;
    // cin>>t2;
    for(int i=1;i<=t2;i++){
        test();
    }
}

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