oj.uz

Submission #440314

# Submission time Handle Problem Language Result Execution time Memory
440314 2021-07-02T03:33:53 Z 최서현(#7495) Bodyguard (JOI21_bodyguard) C++17
100 / 100
 9147 ms 1425848 KB 
#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

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7302 ms 820144 KB Output is correct
2 Correct 6895 ms 822468 KB Output is correct
3 Correct 2397 ms 372792 KB Output is correct
4 Correct 1751 ms 226216 KB Output is correct
5 Correct 3441 ms 1289088 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2003 ms 1106916 KB Output is correct
2 Correct 1977 ms 1106936 KB Output is correct
3 Correct 1932 ms 1091828 KB Output is correct
4 Correct 3 ms 1612 KB Output is correct
5 Correct 1868 ms 1106820 KB Output is correct
6 Correct 1819 ms 1106888 KB Output is correct
7 Correct 1845 ms 1105280 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2003 ms 1106916 KB Output is correct
2 Correct 1977 ms 1106936 KB Output is correct
3 Correct 1932 ms 1091828 KB Output is correct
4 Correct 3 ms 1612 KB Output is correct
5 Correct 1868 ms 1106820 KB Output is correct
6 Correct 1819 ms 1106888 KB Output is correct
7 Correct 1845 ms 1105280 KB Output is correct
8 Correct 1972 ms 1107104 KB Output is correct
9 Correct 1995 ms 1107104 KB Output is correct
10 Correct 2011 ms 1089932 KB Output is correct
11 Correct 6 ms 1892 KB Output is correct
12 Correct 1864 ms 1107136 KB Output is correct
13 Correct 1837 ms 1107128 KB Output is correct
14 Correct 1869 ms 1106996 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2003 ms 1106916 KB Output is correct
2 Correct 1977 ms 1106936 KB Output is correct
3 Correct 1932 ms 1091828 KB Output is correct
4 Correct 3 ms 1612 KB Output is correct
5 Correct 1868 ms 1106820 KB Output is correct
6 Correct 1819 ms 1106888 KB Output is correct
7 Correct 1845 ms 1105280 KB Output is correct
8 Correct 1972 ms 1107104 KB Output is correct
9 Correct 1995 ms 1107104 KB Output is correct
10 Correct 2011 ms 1089932 KB Output is correct
11 Correct 6 ms 1892 KB Output is correct
12 Correct 1864 ms 1107136 KB Output is correct
13 Correct 1837 ms 1107128 KB Output is correct
14 Correct 1869 ms 1106996 KB Output is correct
15 Correct 2106 ms 1111480 KB Output is correct
16 Correct 2096 ms 1111568 KB Output is correct
17 Correct 1976 ms 1096728 KB Output is correct
18 Correct 23 ms 5052 KB Output is correct
19 Correct 1923 ms 1110444 KB Output is correct
20 Correct 1878 ms 1110208 KB Output is correct
21 Correct 2023 ms 1109680 KB Output is correct

Subtask #5
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 7302 ms 820144 KB Output is correct
2 Correct 6895 ms 822468 KB Output is correct
3 Correct 2397 ms 372792 KB Output is correct
4 Correct 1751 ms 226216 KB Output is correct
5 Correct 3441 ms 1289088 KB Output is correct
6 Correct 2003 ms 1106916 KB Output is correct
7 Correct 1977 ms 1106936 KB Output is correct
8 Correct 1932 ms 1091828 KB Output is correct
9 Correct 3 ms 1612 KB Output is correct
10 Correct 1868 ms 1106820 KB Output is correct
11 Correct 1819 ms 1106888 KB Output is correct
12 Correct 1845 ms 1105280 KB Output is correct
13 Correct 1972 ms 1107104 KB Output is correct
14 Correct 1995 ms 1107104 KB Output is correct
15 Correct 2011 ms 1089932 KB Output is correct
16 Correct 6 ms 1892 KB Output is correct
17 Correct 1864 ms 1107136 KB Output is correct
18 Correct 1837 ms 1107128 KB Output is correct
19 Correct 1869 ms 1106996 KB Output is correct
20 Correct 2106 ms 1111480 KB Output is correct
21 Correct 2096 ms 1111568 KB Output is correct
22 Correct 1976 ms 1096728 KB Output is correct
23 Correct 23 ms 5052 KB Output is correct
24 Correct 1923 ms 1110444 KB Output is correct
25 Correct 1878 ms 1110208 KB Output is correct
26 Correct 2023 ms 1109680 KB Output is correct
27 Correct 9147 ms 1425848 KB Output is correct
28 Correct 8467 ms 1425812 KB Output is correct
29 Correct 4603 ms 1343468 KB Output is correct
30 Correct 1512 ms 238560 KB Output is correct
31 Correct 3388 ms 1265916 KB Output is correct
32 Correct 4956 ms 1356720 KB Output is correct
33 Correct 3132 ms 1306944 KB Output is correct