Submission #815883

#	Time	Username	Problem	Language	Result	Execution time	Memory
815883		Cookie	Garden (JOI23_garden)	C++14	100 / 100	566 ms	108124 KiB

garden

#include<bits/stdc++.h>
#include<fstream>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const int base = 74;
const ll mod = 1e9 + 7, inf = 1e9, mxv = 1005, mxn = 5e5 + 5;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, m, d;
int a[mxn + 1], b[mxn + 1], x[mxn + 1], y[mxn + 1], res[5005][5005];
bool need[5005], vis[5005];
vt<int>pos[5005], rem[10005];
struct Cool{
    bool ok[10005];
    int l[10005], r[10005], mx = 0;
    void init(){
        mx = 0;
        for(int i = 0; i < 2 * d; i++){
            ok[i] = 0; l[i] = r[i] = i;
        }
    }
    void add(int x){
        ok[x] = 1;
        if(x && ok[x - 1] && ok[x + 1]){
            r[l[x - 1]] = r[x + 1]; l[r[x + 1]] = l[x - 1];
            r[x] = r[x + 1]; l[x] = l[x - 1];
        }else if(x && ok[x - 1]){
            r[l[x - 1]] = x; l[x] = l[x - 1];
        }else if(ok[x + 1]){
            l[r[x + 1]] = x; r[x] = r[x + 1]; 
        }
        mx = max(mx, r[x] - l[x] + 1);
    }
};
Cool comp;
int getid(int x){
    if(x < d)return(x);
    return(x - d);
}
signed main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> d;
    for(int i = 1; i <= n; i++)cin >> a[i] >> b[i];
    for(int i = 1; i <= m; i++){
        cin >> x[i] >> y[i]; pos[x[i]].pb(y[i]);
    }
    for(int i = 1; i <= n; i++){
        need[b[i]] = 1; vis[a[i]] = 1;
    }
    vt<int>cand(d, -1);
    for(int i = 0; i < d; i++){
        for(auto j: pos[i]){
            cand[j] = i;
        }
    }
    for(int i = 0; i < d; i++){
        res[0][i] = cand[i];
    }
    for(int i = 1; i < d; i++){
        for(auto j: pos[getid(i + d - 1)]){
            cand[j] = i + d - 1;
        }
        for(int j = 0; j < d; j++){
            res[i][j] = cand[j];
        }
    }
    ll ans = inf;
    for(int i = 0; i < d; i++){
        comp.init();
        int last = i;
        for(int j = i; j < i + d; j++){
            if(vis[getid(j)])last = j;
        }
        for(int j = i; j < i + d; j++)rem[j].clear();
        for(int j = 0; j < d; j++){
            if(!need[j]){
                if(res[i][j] <= last){
                    comp.add(j); comp.add(j + d);
                }else{
                    rem[res[i][j]].pb(j);
                }
 
            }
        }
        for(int j = last; j <= i + d - 1; j++){
            ll cand_ans = (d - comp.mx) * (j - i + 1);
            ans = min(ans, cand_ans);
            if(j != i + d - 1){
                for(auto k: rem[j + 1]){
                    comp.add(k); comp.add(k + d);
                }
            }
 
        }
    }
    cout << ans;
    return(0);
}

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