제출 #1164274

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1164274		dragst	Garden (JOI23_garden)	C++20	15 / 100	274 ms	20408 KiB

garden

#include <bits/stdc++.h>
using namespace std;

const long long inf=1e9;
long long d, p[500005], q[500005], r[500005], s[500005], id[500005], nxt[5005], pre[5005], check[5005], check2[5005], mn;
vector<long long> v1, v2, v[5005];

bool sortt(long long x, long long y) {return p[x]<p[y];}

void build()
{
    mn=1e9;
    long long n=v2.size(), i;
    for (i=1; i<n; i++)
    {
        check[v2[i]]=check2[v2[i]];
        pre[v2[i]]=v2[i-1];
        nxt[v2[i-1]]=v2[i];
        mn=min(mn, v2[i-1]+d-v2[i]+1);
    };
    pre[v2[0]]=v2[n-1];
    nxt[v2[n-1]]=v2[0];
    check[v2[0]]=check2[v2[0]];
    mn=min(mn, v2[n-1]-v2[0]+1);
}

void del(long long x)
{
    mn=min(mn, (pre[x]+d-nxt[x])%d+1);
    pre[nxt[x]]=pre[x];
    nxt[pre[x]]=nxt[x];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n, m, i, j, ans=inf;
    cin >> n >> m >> d;
    for (i=1; i<=n; i++)
    {
        cin >> p[i] >> q[i];
        id[i]=i;
        v1.push_back(p[i]);
        v2.push_back(q[i]);
        check2[q[i]]++;
    };
    sort(id+1, id+n+1, sortt);
    for (i=1; i<=m; i++)
    {
        cin >> r[i] >> s[i];
        v1.push_back(r[i]);
        v2.push_back(s[i]);
        v[r[i]].push_back(s[i]);
        check2[s[i]]++;
    };
    sort(v1.begin(), v1.end());
    v1.erase(unique(v1.begin(), v1.end()), v1.end());
    sort(v2.begin(), v2.end());
    v2.erase(unique(v2.begin(), v2.end()), v2.end());
    for (i=0; i<d; i++)
    {
        sort(v[i].begin(), v[i].end());
        v[i].erase(unique(v[i].begin(), v[i].end()), v[i].end());
    };
    j=1;
    p[0]=p[id[n]]-d; q[0]=q[id[n]]-d;
    for (auto x: v1)
    {
        while (j<=n && p[id[j]]<x) {j++;};
        build();
        for (i=x; i<x+d; i++)
        {
            for (auto y: v[i%d])
            {
                check[y]--;
                if (check[y]==0) {del(y);};
            };
            if (i-d>=p[id[j-1]]) {ans=min(ans, (i-x+1)*mn);};
        };
    };
    cout << ans;
}

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