Submission #1196302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196302		LGQ_A3K25	Cultivation (JOI17_cultivation)	C++17	80 / 100	2097 ms	2276 KiB

cultivation

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a*b / __gcd(a,b)
#define I first
#define II second
#define pb push_back
#define ii pair<int,int>
const int INF = 2e9;
const int N = 3e2 + 5;
const int MOD = 1e9 + 7;
int n, m, k;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll Rand(ll l,ll r)
{
    ll k = rd() * rd();
    if (k < 0) k = -k;
    return l + k % (r - l + 1);
}
int tg[N], num[2 * N];
ll ans = 1e18;
ii p[N];
array<int, 3> cur[2 * N], f[N][N]; // L, R, M
struct DQ
{
    deque<ii> q;
    inline void add(ii x)
    {
        while (q.size() && q.back().I <= x.I) q.pop_back();
        q.pb(x);
    }
    inline void del(int& x)
    {
        while (q.size() && q.front().II <= x) q.pop_front();
    }
    inline int get()
    {
        if (q.empty()) return INF; else
            return q.front().I;
    }
} L, R, M;
inline void init()
{
    for (int l = 1; l <= k; l++)
    {
        int sz = 0;
        for (int r = l; r <= k; r++)
        {
            int mx = p[r].II;
            for (int i = 1; i <= sz; i++)
                if (mx < tg[i]) swap(tg[i], mx);
            tg[++sz] = mx;
            f[l][r][0] = tg[1] - 1;
            f[l][r][1] = m - tg[sz];
            for (int i = 1; i < sz; i++)
                f[l][r][2] = max(f[l][r][2], tg[i + 1] - tg[i] - 1);
//                cout << l << ' ' << r << ' ' << f[l][r][0] << ' ' << f[l][r][1] << ' ' << f[l][r][2] << '\n';
        }
    }
}
inline void solve(int le)
{
    if (le >= ans) return;
    int sz = 0;
    for (int l = 1, r = 1; l <= k; l++)
    {
        while (r <= k && p[r].I <= p[l].I + le)
        {
            int val = p[r++].I;
            if (val > num[sz]) num[++sz] = val;
        }
        if (p[l].I + le + 1 > num[sz]) num[++sz] = p[l].I + le + 1;
    }
    for (int i = 1, l = 1, r = 1; i <= sz; i++)
    {
        while (l <= k && !(p[l].I <= num[i] && num[i] <= p[l].I + le)) l++;
        r = max(r, l);
        while (r <= k && p[r].I <= num[i] && num[i] <= p[r].I + le) r++;
        if (l > k) cur[i] = {INF, INF, INF}; else
            cur[i] = f[l][r - 1];
    }
    for (int l = 1, r = 1; l <= sz; l++)
    {
        r = max(r, l);
        while (r <= sz && num[r] < num[l] + n)
        {
            L.add({cur[r][0], r});
            R.add({cur[r][1], r});
            M.add({cur[r][2], r++});
        }
//            cout << le << ' ' << L.get() << ' ' << R.get() << ' ' << M.get() << '\n';
        ans = min(ans, 0ll + le + max(L.get() + R.get(), M.get()));
        L.del(l);
        R.del(l);
        M.del(l);
    }
}
void sub3()
{
    for (int i = 1; i <= k; i++) cin >> p[i].I >> p[i].II;
    vector<int> t;
    sort(p + 1, p + k + 1);
    for (int i = 1; i <= k; i++)
    {
        t.pb(p[i].I - 1);
        t.pb(n - p[i].I);
        for (int j = 1; j <= k; j++)
        {
            t.pb(max(0, p[j].I - p[i].I - 1));
            t.pb(p[i].I - 1 + n - p[j].I);
        }
    }
    sort(t.begin(), t.end());
    t.resize(unique(t.begin(), t.end()) - t.begin());
//        for (auto c : t) cout << c << ' ';cout << '\n';
    init();
    for (auto l : t) solve(l);
    cout << ans;
}
int32_t main()
{
#define TASKNAME ""
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (fopen(TASKNAME".inp","r" ))
    {
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".ans","w",stdout);
    }
    cin >> n >> m >> k;
//    if (max(n, m) <= 40) sub1 :: main(); else
//        if (k <= 25) sub2 :: main(); else
            sub3();
    return 0;
}

Compilation message (stderr)

cultivation.cpp: In function 'int32_t main()':
cultivation.cpp:132:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:133:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |         freopen(TASKNAME".ans","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 30 / 30
• Subtask 5: 20 / 20
• Subtask 6: 0 / 20