Submission #815716

#	Time	Username	Problem	Language	Result	Execution time	Memory
815716		jeff252	Garden (JOI23_garden)	C++14	100 / 100	324 ms	6324 KiB

garden

#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=5e3+10;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e16;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=2027865967;
const ll p=70032301;
const ull p2=913;
const int L=20;
int t[N],n,m,d;
pair<int,int> li[N];
bitset<N> tr[N],m1,m2,moz;
vi g[N*2];
void solve(){
    cin>>n>>m>>d;
    for(int i=1;i<=n;i++){
        int a,b;
        cin>>a>>b;
        m1[a]=1,m2[b]=1;
    }
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        tr[a][b]=1;
        moz[b]=1;
    }
    for(int i=0;i<d;i++){
        if(m2[i]) continue;
        for(int i2=d*2-1;i2>=d;i2--){
            if(tr[i2-d][i]){
                g[i2].push_back(i);
                break;
            }
        }
    }
    int res=INFi;
    for(int i=d-1;i>=0;i--){
        for(auto u:g[i+d]){
            for(int i2=i+d-1;i2>=i;i2--){
                int id=(i2>=d?i2-d:i2); 
                if(tr[id][u]){
                    g[i2].push_back(u);
                    break;
                }
            }
        }
        int pop=-1,maxir=0;
        for(int i2=0;i2<d;i2++){
            li[i2].fi=pop;
            if(m2[i2] or moz[i2]) pop=i2;
        }        
        int ost=pop;
        pop=-1;
        for(int i2=d-1;i2>=0;i2--){
            li[i2].se=pop;
            if(pop!=-1){
                maxir=max(maxir,pop-i2-1);
            }
            if(m2[i2] or moz[i2]) pop=i2;
        }
        int pierw=pop,pom=0;
        for(int i2=i;i2<i+d;i2++){
            int id=(i2>=d?i2-d:i2);
            if(m1[id]) pom=i2;
        }
        for(int i2=i;i2<i+d;i2++){
            for(auto u:g[i2]){
                if(li[u].fi==-1){
                    pierw=li[u].se;
                    li[li[u].se].fi=-1;
                }
                if(li[u].se==-1){
                    ost=li[u].fi;
                    li[li[u].fi].se=-1;
                }
                if(li[u].se!=-1 and li[u].fi!=-1){
                    maxir=max(maxir,li[u].se-li[u].fi-1);
                    li[li[u].fi].se=li[u].se;
                    li[li[u].se].fi=li[u].fi;
                }
            } 
            if(i2>=pom){
                res=min(res,(i2-i+1)*min(d-maxir,ost-pierw+1));
            }
        }
    }
    cout<<res<<"\n";
}
int main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    int tt=1;
    while(tt--) solve();
}

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