oj.uz

Submission #433188

# Submission time Handle Problem Language Result Execution time Memory
433188 2021-06-19T06:34:37 Z CodePlatina Bodyguard (JOI21_bodyguard) C++17
100 / 100
 8692 ms 1425644 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 6546 ms 793088 KB Output is correct
2 Correct 6423 ms 825532 KB Output is correct
3 Correct 2444 ms 372968 KB Output is correct
4 Correct 1733 ms 226288 KB Output is correct
5 Correct 3491 ms 1293924 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2069 ms 1106688 KB Output is correct
2 Correct 2009 ms 1106808 KB Output is correct
3 Correct 1965 ms 1091704 KB Output is correct
4 Correct 4 ms 1612 KB Output is correct
5 Correct 1913 ms 1106856 KB Output is correct
6 Correct 1865 ms 1106808 KB Output is correct
7 Correct 1917 ms 1105220 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2069 ms 1106688 KB Output is correct
2 Correct 2009 ms 1106808 KB Output is correct
3 Correct 1965 ms 1091704 KB Output is correct
4 Correct 4 ms 1612 KB Output is correct
5 Correct 1913 ms 1106856 KB Output is correct
6 Correct 1865 ms 1106808 KB Output is correct
7 Correct 1917 ms 1105220 KB Output is correct
8 Correct 2033 ms 1107156 KB Output is correct
9 Correct 2001 ms 1107072 KB Output is correct
10 Correct 1994 ms 1089928 KB Output is correct
11 Correct 7 ms 1868 KB Output is correct
12 Correct 1938 ms 1107192 KB Output is correct
13 Correct 1884 ms 1107116 KB Output is correct
14 Correct 1983 ms 1107104 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2069 ms 1106688 KB Output is correct
2 Correct 2009 ms 1106808 KB Output is correct
3 Correct 1965 ms 1091704 KB Output is correct
4 Correct 4 ms 1612 KB Output is correct
5 Correct 1913 ms 1106856 KB Output is correct
6 Correct 1865 ms 1106808 KB Output is correct
7 Correct 1917 ms 1105220 KB Output is correct
8 Correct 2033 ms 1107156 KB Output is correct
9 Correct 2001 ms 1107072 KB Output is correct
10 Correct 1994 ms 1089928 KB Output is correct
11 Correct 7 ms 1868 KB Output is correct
12 Correct 1938 ms 1107192 KB Output is correct
13 Correct 1884 ms 1107116 KB Output is correct
14 Correct 1983 ms 1107104 KB Output is correct
15 Correct 2100 ms 1111508 KB Output is correct
16 Correct 2132 ms 1111572 KB Output is correct
17 Correct 2054 ms 1096700 KB Output is correct
18 Correct 22 ms 5052 KB Output is correct
19 Correct 1938 ms 1110480 KB Output is correct
20 Correct 1899 ms 1110276 KB Output is correct
21 Correct 1973 ms 1109556 KB Output is correct

Subtask #5
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 6546 ms 793088 KB Output is correct
2 Correct 6423 ms 825532 KB Output is correct
3 Correct 2444 ms 372968 KB Output is correct
4 Correct 1733 ms 226288 KB Output is correct
5 Correct 3491 ms 1293924 KB Output is correct
6 Correct 2069 ms 1106688 KB Output is correct
7 Correct 2009 ms 1106808 KB Output is correct
8 Correct 1965 ms 1091704 KB Output is correct
9 Correct 4 ms 1612 KB Output is correct
10 Correct 1913 ms 1106856 KB Output is correct
11 Correct 1865 ms 1106808 KB Output is correct
12 Correct 1917 ms 1105220 KB Output is correct
13 Correct 2033 ms 1107156 KB Output is correct
14 Correct 2001 ms 1107072 KB Output is correct
15 Correct 1994 ms 1089928 KB Output is correct
16 Correct 7 ms 1868 KB Output is correct
17 Correct 1938 ms 1107192 KB Output is correct
18 Correct 1884 ms 1107116 KB Output is correct
19 Correct 1983 ms 1107104 KB Output is correct
20 Correct 2100 ms 1111508 KB Output is correct
21 Correct 2132 ms 1111572 KB Output is correct
22 Correct 2054 ms 1096700 KB Output is correct
23 Correct 22 ms 5052 KB Output is correct
24 Correct 1938 ms 1110480 KB Output is correct
25 Correct 1899 ms 1110276 KB Output is correct
26 Correct 1973 ms 1109556 KB Output is correct
27 Correct 8692 ms 1416364 KB Output is correct
28 Correct 8449 ms 1425644 KB Output is correct
29 Correct 4660 ms 1343832 KB Output is correct
30 Correct 1424 ms 238376 KB Output is correct
31 Correct 3669 ms 1267168 KB Output is correct
32 Correct 4971 ms 1357384 KB Output is correct
33 Correct 3344 ms 1308996 KB Output is correct