首页 > 其他分享 >P4154

P4154

时间:2024-04-01 15:23:16浏览次数:27  
标签:int rep mi second P4154 first define

令所有的 \(w<h\) ,一个集合的 \(res=min(w)\times min(h)\)

按 \(w\) 排序,假设一开始的分组为 \([1,n],[n+1,2n]\),每次考虑加一个数到后一个区间内,就要维护后缀区间的第 \(n+1\) 大和第 \(n\) 大的数,考虑用 \(2\) 个multiset 维护,并预处理前缀 \(h\) 的 \(min\)

// Author: xiaruize
#ifndef ONLINE_JUDGE
#define debug(x) cerr << "On Line:" << __LINE__ << #x << "=" << x << endl
bool start_of_memory_use;
#else
#define debug(x)
#endif
#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
clock_t start_clock = clock();
#endif
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b)

{
    if (a > b)
        return a;
    return b;
}
int min(int a, int b)
{
    if (a < b)
        return a;
    return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 2e5 + 10;

int n, m;
pii a[N];
int x[N], y[N];
int XA, XB, XC;
int YA, YB, YC;
int mi[N];
multiset<int> s, t;

bool cmp(pii a, pii b)
{
    return a.second < b.second;
}

void solve()
{
    cin >> n;
    n *= 2;
    cin >> m;
    rep(i, 1, m) cin >> x[i];
    cin >> m;
    rep(i, 1, m) cin >> y[i];
    cin >> XA >> XB >> XC >> YA >> YB >> YC;
    rep(i, m + 1, n)
    {
        x[i] = (x[i - 1] * XA + XB) % XC + 1;
        y[i] = (y[i - 1] * YA + YB) % YC + 1;
    }
    int maxn = 0;
    rep(i, 1, n)
    {
        if (x[i] > y[i])
            swap(x[i], y[i]);
        a[i] = {x[i], y[i]};
    }
    sort(a + 1, a + n + 1);
    mi[0] = INF;
    rep(i, 1, n) mi[i] = min(mi[i - 1], a[i].second);
    rep(i, n / 2 + 1, n)
    {
        s.insert(a[i].second);
        t.insert(a[i].second);
    }
    int res = a[1].first * mi[n / 2] + a[n / 2 + 1].first * (*t.begin());
    per(i, n / 2, 1)
    {
        s.insert(a[i].second);
        while (s.size() > n / 2 + 1)
            s.erase(prev(s.end()));
        t.insert(a[i].second);
        while (t.size() > n / 2)
            t.erase(t.begin());
        res = max(res, a[1].first * min(mi[i - 1], *s.rbegin()) + a[i].first * (*s.begin()));
        res = max(res, a[1].first * min(mi[i - 1], *s.begin()) + a[i].first * (*t.begin()));
    }
    cout << res << endl;
}

#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int testcase = 1;
    // cin >> testcase;
    while (testcase--)
        solve();
#ifndef ONLINE_JUDGE
    cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
    cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
    return 0;
}

标签:int,rep,mi,second,P4154,first,define
From: https://www.cnblogs.com/xiaruize/p/18108513

相关文章