Submission #433188

#	Time	Username	Problem	Language	Result	Execution time	Memory
433188		CodePlatina	Bodyguard (JOI21_bodyguard)	C++17	100 / 100	8692 ms	1425644 KiB

bodyguard

#define ON
#ifdef ON
#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <cstdlib>
#include <random>
#include <chrono>
#include <functional>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define piii pair<int, pii>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss

using namespace std;

uniform_int_distribution<int> dis(1, (int)1e9);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
auto rnd = bind(dis, rng);

const long long INF = (long long)1e9 + 7;

struct line
{
    long long a, b;
    line(void) : a(0), b(0) {}
    long long eval(long long x) { return a * x + b; }
};

vector<long long> main1(int n, int T, vector<tiiii> A, vector<pii> qr)
{
//    ios_base::sync_with_stdio(false);
//    cin.tie(nullptr);
//
//    freopen("in.txt", "r", stdin);

//    int n, T; cin >> n >> T;
//    tiiii A[n];
//    for(auto &[a, b, c, d] : A) cin >> a >> b >> c >> d;

    vector<long long> prX, prY;
    for(auto &[a, b, c, d] : A)
    {
        if(b < c)
        {
            prX.push_back(1ll * a + b);
            prX.push_back(1ll * a - b + 2 * c);
            prY.push_back(1ll * a - b + INF);
        }
        else
        {
            prX.push_back(1ll * a + b);
            prY.push_back(1ll * a - b + INF);
            prY.push_back(1ll * a + b - 2 * c + INF);
        }
    }
    prX.push_back(INF * 3);
    prX.push_back(-1);
    prY.push_back(INF * 3);
    prY.push_back(-1);
    sort(prX.begin(), prX.end());
    sort(prY.begin(), prY.end());
    prX.resize(unique(prX.begin(), prX.end()) - prX.begin());
    prY.resize(unique(prY.begin(), prY.end()) - prY.begin());

    int N = prX.size(), M = prY.size();
    int CX[N + 1][M + 1]{}, CY[N + 1][M + 1]{};
    for(auto &[a, b, c, d] : A)
    {
        if(b < c)
        {
            int x1 = lower_bound(prX.begin(), prX.end(), 1ll * a + b) - prX.begin();
            int x2 = lower_bound(prX.begin(), prX.end(), 1ll * a - b + 2 * c) - prX.begin();
            int y = lower_bound(prY.begin(), prY.end(), 1ll * a - b + INF) - prY.begin();
            for(int j = x1; j < x2; ++j) CX[j][y] = max(CX[j][y], d / 2);
        }
        else
        {
            int x = lower_bound(prX.begin(), prX.end(), 1ll * a + b) - prX.begin();
            int y1 = lower_bound(prY.begin(), prY.end(), 1ll * a - b + INF) - prY.begin();
            int y2 = lower_bound(prY.begin(), prY.end(), 1ll * a + b - 2 * c + INF) - prY.begin();
            for(int j = y1; j < y2; ++j) CY[x][j] = max(CY[x][j], d / 2);
        }
    }

    long long dp[N + 1][M + 1]{};
    for(int i = N; i >= 0; --i)
    {
        for(int j = M; j >= 0; --j)
        {
            if(i < N) dp[i][j] = max(dp[i][j], dp[i + 1][j] + 1ll * CX[i][j] * (prX[i + 1] - prX[i]));
            if(j < M) dp[i][j] = max(dp[i][j], dp[i][j + 1] + 1ll * CY[i][j] * (prY[j + 1] - prY[j]));
        }
    }

//    for(int i = 0; i <= N; ++i)
//    {
//        for(int j = 0; j <= M; ++j)
//            cout << dp[i][j] << ' ';
//        cout << endl;
//    }

    vector<pll> lsX[N + 1][M + 1], lsY[N + 1][M + 1];
    for(int i = 0; i < T; ++i)
    {
//        int x, y; cin >> x >> y;
        int x = qr[i].ff, y = qr[i].ss;
        int xi = lower_bound(prX.begin(), prX.end(), x + y) - prX.begin();
        int yi = lower_bound(prY.begin(), prY.end(), x - y + INF) - prY.begin();
        lsX[xi][yi].push_back({prX[xi] - x - y, i});
        lsY[xi][yi].push_back({prY[yi] - x + y - INF, i});
    }

    vector<line> S;

    vector<long long> ans(T);
    for(int i = 1; i <= N; ++i)
    {
        S.clear();
        S.emplace_back();

        for(int j = M; j >= 0; --j)
        {
            line tmp;
            tmp.a = CX[i - 1][j];
            tmp.b = dp[i][j];

            while(S.size() >= 2)
            {
                long long x = S[S.size() - 1].b - S[S.size() - 2].b;
                long long y = S[S.size() - 2].a - S[S.size() - 1].a;
                long long z = tmp.b - S[S.size() - 1].b;
                long long w = S[S.size() - 1].a - tmp.a;
//                cout << x * w << ' ' << y * z << endl;
                if(w <= 0 || (long double)x / y < (long double)z / w) S.pop_back();
                else break;
            }
            if(S.back().b == tmp.b) S.back().a = max(S.back().a, tmp.a);
            else if(S.back().a <= tmp.a) S.back() = tmp;
            else S.push_back(tmp);

            for(auto [x, q] : lsX[i][j])
            {
                int s = 0, e = S.size();
                while(s + 1 < e)
                {
                    int mid = s + e >> 1;
                    long long y = S[mid].b - S[mid - 1].b;
                    long long z = S[mid - 1].a - S[mid].a;
                    if(x < (long double)y / z) s = mid;
                    else e = mid;
                }
                ans[q] = max(ans[q], S[s].eval(x));
            }
        }
    }
    for(int j = 1; j <= M; ++j)
    {
        S.clear();
        S.emplace_back();

        for(int i = N; i >= 0; --i)
        {
            line tmp;
            tmp.a = CY[i][j - 1];
            tmp.b = dp[i][j];
            while(S.size() >= 2)
            {
                long long x = S[S.size() - 1].b - S[S.size() - 2].b;
                long long y = S[S.size() - 2].a - S[S.size() - 1].a;
                long long z = tmp.b - S[S.size() - 1].b;
                long long w = S[S.size() - 1].a - tmp.a;
//                cout << x * w << ' ' << y * z << endl;
                if(w <= 0 || (long double)x / y < (long double)z / w) S.pop_back();
                else break;
            }
            if(S.back().b == tmp.b) S.back().a = max(S.back().a, tmp.a);
            else if(S.back().a <= tmp.a) S.back() = tmp;
            else S.push_back(tmp);

            for(auto [x, q] : lsY[i][j])
            {
                int s = 0, e = S.size();
                while(s + 1 < e)
                {
                    int mid = s + e >> 1;
                    long long y = S[mid].b - S[mid - 1].b;
                    long long z = S[mid - 1].a - S[mid].a;
                    if(x < (long double)y / z) s = mid;
                    else e = mid;
                }
                ans[q] = max(ans[q], S[s].eval(x));
            }
        }
    }

//    for(auto i : ans) cout << i << '\n';
    return ans;
}


//#else
#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define piii pair<int, pii>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss

using namespace std;

vector<long long> main2(int n, int T, vector<tiiii> A, vector<pii> qr)
{
//    ios_base::sync_with_stdio(false);
//    cin.tie(nullptr);
//
//    freopen("in.txt", "r", stdin);
//
//    int n, T; cin >> n >> T;
//    tiiii A[n];
//    for(auto &[a, b, c, d] : A) cin >> a >> b >> c >> d;

    vector<long long> prX, prY;
    for(auto &[a, b, c, d] : A)
    {
        if(b < c)
        {
            prX.push_back(1ll * a + b);
            prX.push_back(1ll * a - b + 2 * c);
            prY.push_back(1ll * a - b);
        }
        else
        {
            prX.push_back(1ll * a + b);
            prY.push_back(1ll * a + b - 2 * c);
            prY.push_back(1ll * a - b);
        }
    }
    prX.push_back((long long)4e9+7);
    prY.push_back((long long)4e9+7);
    sort(prX.begin(), prX.end());
    sort(prY.begin(), prY.end());
    prX.resize(unique(prX.begin(), prX.end()) - prX.begin());
    prY.resize(unique(prY.begin(), prY.end()) - prY.begin());

    int N = prX.size(), M = prY.size();
    int CX[N + 1][M + 1]{}, CY[N + 1][M + 1]{};
    for(auto &[a, b, c, d] : A)
    {
        if(b < c)
        {
            int x1 = lower_bound(prX.begin(), prX.end(), 1ll * a + b) - prX.begin();
            int x2 = lower_bound(prX.begin(), prX.end(), 1ll * a - b + 2 * c) - prX.begin();
            int y = lower_bound(prY.begin(), prY.end(), 1ll * a - b) - prY.begin();
            for(int j = x1; j < x2; ++j) CX[j][y] = max(CX[j][y], d / 2);
        }
        else
        {
            int x = lower_bound(prX.begin(), prX.end(), 1ll * a + b) - prX.begin();
            int y1 = lower_bound(prY.begin(), prY.end(), 1ll * a - b) - prY.begin();
            int y2 = lower_bound(prY.begin(), prY.end(), 1ll * a + b - 2 * c) - prY.begin();
            for(int j = y1; j < y2; ++j) CY[x][j] = max(CY[x][j], d / 2);
        }
    }

    long long dp[N + 1][M + 1]{};
    for(int i = N; i >= 0; --i)
    {
        for(int j = M; j >= 0; --j)
        {
            if(i < N) dp[i][j] = max(dp[i][j], dp[i + 1][j] + 1ll * CX[i][j] * (prX[i + 1] - prX[i]));
            if(j < M) dp[i][j] = max(dp[i][j], dp[i][j + 1] + 1ll * CY[i][j] * (prY[j + 1] - prY[j]));
        }
    }

//    for(int i = 0; i <= N; ++i)
//    {
//        for(int j = 0; j <= M; ++j)
//            cout << dp[i][j] << ' ';
//        cout << endl;
//    }

    vector<pll> lsX[N + 1][M + 1], lsY[N + 1][M + 1];
    for(int i = 0; i < T; ++i)
    {
//        int x, y; cin >> x >> y;
        int x = qr[i].ff, y = qr[i].ss;
        int xi = lower_bound(prX.begin(), prX.end(), x + y) - prX.begin();
        int yi = lower_bound(prY.begin(), prY.end(), x - y) - prY.begin();
        lsX[xi][yi].push_back({prX[xi] - x - y, i});
        lsY[xi][yi].push_back({prY[yi] - x + y, i});
    }

    vector<long long> ans(T);
    for(int i = 0; i <= N; ++i)
    {
        for(int j = 0; j <= M; ++j)
        {
            for(auto [x, q] : lsX[i][j])
                for(int k = j; k <= M; ++k) ans[q] = max(ans[q], dp[i][k] + 1ll * x * (i ? CX[i - 1][k] : 0));
            for(auto [x, q] : lsY[i][j])
                for(int k = i; k <= N; ++k) ans[q] = max(ans[q], dp[k][j] + 1ll * x * (j ? CY[k][j - 1] : 0));
        }
    }

//    for(auto i : ans) cout << i << '\n';
    return ans;
}

void input(int &n, int &T, vector<tiiii> &A, vector<pii> &qr)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

//    freopen("in.txt", "r", stdin);

    cin >> n >> T;
    A.resize(n);
    for(auto &[a, b, c, d] : A) cin >> a >> b >> c >> d;
    qr.resize(T);
    for(auto &[a, b] : qr) cin >> a >> b;
}

void gen(int &n, int &T, vector<tiiii> &A, vector<pii> &qr)
{
    n = 10;
    T = 10;
    A.resize(n);
    for(auto &[a, b, c, d] : A)
    {
        a = rnd();
        b = rnd();
        c = rnd();
        d = rnd() * 2;
    }
    qr.resize(T);
    for(auto &[a, b] : qr)
    {
        a = rnd();
        b = rnd();
    }
}

int main()
{
    int n, T;
    vector<tiiii> A;
    vector<pii> qr;

    input(n, T, A, qr);
    auto ans = main1(n, T, A, qr);

    for(auto i : ans) cout << i << '\n';

//    for(int i = 0; i < 101; ++i)
//    {
//        gen(n, T, A, qr);
//        if(main1(n, T, A, qr) != main2(n, T, A, qr))
//        {
//            freopen("in.txt", "w", stdout);
//            cout << n << ' ' << T << endl;
//            for(auto [a, b, c, d] : A) cout << a << ' ' << b << ' ' << c << ' ' << d << endl;
//            for(auto [a, b] : qr) cout << a << ' ' << b << endl;
//            return 0;
//        }
////        cout << "ok" << endl;
//    }
//    cout << "sad.." << endl;
}

#endif

Compilation message (stderr)

bodyguard.cpp: In function 'std::vector<long long int> main1(int, int, std::vector<std::tuple<int, int, int, int> >, std::vector<std::pair<int, int> >)':
bodyguard.cpp:153:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  153 |                     int mid = s + e >> 1;
      |                               ~~^~~
bodyguard.cpp:192:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  192 |                     int mid = s + e >> 1;
      |                               ~~^~~

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 52 / 52