oj.uz

Submission #634798

# Submission time Handle Problem Language Result Execution time Memory
634798 2022-08-25T04:40:40 Z tamthegod Cake 3 (JOI19_cake3) C++14
100 / 100
 485 ms 151856 KB 
#include<bits/stdc++.h>

#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 2e5 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
vector<int> a;
vector <int> val[maxN * 4];
vector <int> sum[maxN * 4];
int node_cnt = 1;

struct TNode
{
    int l, r;
    int lp, rp;
    TNode()
    {
        l = r = lp = rp = 0;
    }
    TNode(int _l, int _r)
    {
        l = _l;
        r = _r;
    }
};
TNode wt[maxN * 4];

void build(int id, auto i, auto j, int l, int r)
{
    wt[id].l = l;
    wt[id].r = r;
    if (l == r)
    {
        return;
    }
    val[id].pb(0);
    sum[id].pb(0);
    int mid = (l + r - (l + r < 0)) / 2;
    int _max = l;
    int _min = r;
    for(auto it = i; it != j; ++it)
    {
        val[id].pb(val[id].back() + (*it <= mid));
        sum[id].pb(sum[id].back() + *it * (*it <= mid));
        if (*it <= mid) _max = max(_max, *it);
        else _min = min(_min, *it);
    }
    auto p = stable_partition(i, j,[=](const auto &w)
    {
        return w <= mid;
    });
    wt[id].lp = ++node_cnt;
    wt[id].rp = ++node_cnt;
    build(wt[id].lp, i, p, l, _max);
    build(wt[id].rp, p, j, _min, r);
}

ll get(int k, int i, int j)
{
    if (k == 0) return 0;
    if(j - i + 1 < k) return -oo;
    --i;
    ll res = 0;
    int id = 1;
    int l = wt[id].l, r = wt[id].r;
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (k <= val[id][j] - val[id][i])
        {
            i = val[id][i];
            j = val[id][j];
            id = wt[id].lp;
        }
        else
        {
            res += sum[id][j] - sum[id][i];
            k -= val[id][j] - val[id][i];
            i -= val[id][i];
            j -= val[id][j];
            id = wt[id].rp;
        }
        l = wt[id].l, r = wt[id].r;
    }
    res += k * l;
    return res;
}

int n, m;
pair<int, int> cake[maxN];
int f[maxN];
void ReadInput()
{
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> cake[i].fi >> cake[i].se;
}
void DnC(int l, int r, int optl, int optr)
{
    if(l > r) return;
    int mid = (l + r) / 2;
    int res = -oo, id = -1;
    for(int i=optl; i<=min(optr, mid - m + 1); i++)
    {
        int val = cake[mid].fi + cake[i].fi + -get(m - 2, i + 1, mid - 1) - (cake[mid].se - cake[i].se) * 2;
        if(res < val)
        {
            res = val;
            id = i;
        }
    }
    f[mid] = res;
    DnC(l, mid - 1, optl, id);
    DnC(mid + 1, r, id, optr);
}
void Solve()
{
    sort(cake + 1, cake + n + 1, [](pair<int, int> p, pair<int, int> q)
    {
        return p.se < q.se;
    });
    a.resize(n + 1);
    for(int i=1; i<=n; i++) a[i] = -cake[i].fi;
    build(1, a.begin() + 1, a.end(), *min_element(a.begin() + 1, a.end()), *max_element(a.begin() + 1, a.end()));
    DnC(m, n, 1, n - m + 1);
    cout << *max_element(f + m, f + n + 1);
}
int32_t main()
{
   // freopen("x.inp", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ReadInput();
    Solve();
}

Compilation message

cake3.cpp:36:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   36 | void build(int id, auto i, auto j, int l, int r)
      |                    ^~~~
cake3.cpp:36:28: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   36 | void build(int id, auto i, auto j, int l, int r)
      |                            ^~~~
cake3.cpp: In function 'll get(long long int, long long int, long long int)':
cake3.cpp:76:13: warning: unused variable 'mid' [-Wunused-variable]
   76 |         int mid = (l + r) / 2;
      |             ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 62880 KB Output is correct
2 Correct 28 ms 62856 KB Output is correct
3 Correct 31 ms 62968 KB Output is correct
4 Correct 31 ms 62876 KB Output is correct
5 Correct 30 ms 62936 KB Output is correct
6 Correct 29 ms 62924 KB Output is correct
7 Correct 28 ms 62960 KB Output is correct
8 Correct 29 ms 62932 KB Output is correct
9 Correct 29 ms 62952 KB Output is correct
10 Correct 28 ms 62904 KB Output is correct
11 Correct 28 ms 62888 KB Output is correct
12 Correct 30 ms 63060 KB Output is correct
13 Correct 30 ms 62884 KB Output is correct
14 Correct 30 ms 63080 KB Output is correct
15 Correct 29 ms 62976 KB Output is correct
16 Correct 31 ms 62936 KB Output is correct
17 Correct 29 ms 62924 KB Output is correct
18 Correct 29 ms 62860 KB Output is correct
19 Correct 28 ms 62932 KB Output is correct
20 Correct 28 ms 62932 KB Output is correct
21 Correct 28 ms 62948 KB Output is correct
22 Correct 28 ms 62864 KB Output is correct
23 Correct 29 ms 62884 KB Output is correct
24 Correct 30 ms 62948 KB Output is correct
25 Correct 28 ms 62972 KB Output is correct
26 Correct 28 ms 62948 KB Output is correct
27 Correct 29 ms 62932 KB Output is correct
28 Correct 29 ms 62928 KB Output is correct
29 Correct 32 ms 62888 KB Output is correct
30 Correct 30 ms 62924 KB Output is correct
31 Correct 29 ms 62932 KB Output is correct
32 Correct 27 ms 62908 KB Output is correct
33 Correct 28 ms 62968 KB Output is correct
34 Correct 32 ms 62848 KB Output is correct
35 Correct 28 ms 62932 KB Output is correct
36 Correct 29 ms 62956 KB Output is correct
37 Correct 29 ms 62984 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 62880 KB Output is correct
2 Correct 28 ms 62856 KB Output is correct
3 Correct 31 ms 62968 KB Output is correct
4 Correct 31 ms 62876 KB Output is correct
5 Correct 30 ms 62936 KB Output is correct
6 Correct 29 ms 62924 KB Output is correct
7 Correct 28 ms 62960 KB Output is correct
8 Correct 29 ms 62932 KB Output is correct
9 Correct 29 ms 62952 KB Output is correct
10 Correct 28 ms 62904 KB Output is correct
11 Correct 28 ms 62888 KB Output is correct
12 Correct 30 ms 63060 KB Output is correct
13 Correct 30 ms 62884 KB Output is correct
14 Correct 30 ms 63080 KB Output is correct
15 Correct 29 ms 62976 KB Output is correct
16 Correct 31 ms 62936 KB Output is correct
17 Correct 29 ms 62924 KB Output is correct
18 Correct 29 ms 62860 KB Output is correct
19 Correct 28 ms 62932 KB Output is correct
20 Correct 28 ms 62932 KB Output is correct
21 Correct 28 ms 62948 KB Output is correct
22 Correct 28 ms 62864 KB Output is correct
23 Correct 29 ms 62884 KB Output is correct
24 Correct 30 ms 62948 KB Output is correct
25 Correct 28 ms 62972 KB Output is correct
26 Correct 28 ms 62948 KB Output is correct
27 Correct 29 ms 62932 KB Output is correct
28 Correct 29 ms 62928 KB Output is correct
29 Correct 32 ms 62888 KB Output is correct
30 Correct 30 ms 62924 KB Output is correct
31 Correct 29 ms 62932 KB Output is correct
32 Correct 27 ms 62908 KB Output is correct
33 Correct 28 ms 62968 KB Output is correct
34 Correct 32 ms 62848 KB Output is correct
35 Correct 28 ms 62932 KB Output is correct
36 Correct 29 ms 62956 KB Output is correct
37 Correct 29 ms 62984 KB Output is correct
38 Correct 31 ms 63444 KB Output is correct
39 Correct 30 ms 63564 KB Output is correct
40 Correct 29 ms 63436 KB Output is correct
41 Correct 29 ms 63492 KB Output is correct
42 Correct 31 ms 63516 KB Output is correct
43 Correct 34 ms 63380 KB Output is correct
44 Correct 30 ms 63436 KB Output is correct
45 Correct 31 ms 63572 KB Output is correct
46 Correct 32 ms 63572 KB Output is correct
47 Correct 33 ms 63516 KB Output is correct
48 Correct 31 ms 63508 KB Output is correct
49 Correct 33 ms 63568 KB Output is correct
50 Correct 30 ms 63444 KB Output is correct
51 Correct 31 ms 63532 KB Output is correct
52 Correct 30 ms 63444 KB Output is correct
53 Correct 30 ms 63444 KB Output is correct
54 Correct 31 ms 63492 KB Output is correct
55 Correct 30 ms 63532 KB Output is correct
56 Correct 30 ms 63544 KB Output is correct
57 Correct 29 ms 63444 KB Output is correct
58 Correct 29 ms 63536 KB Output is correct
59 Correct 29 ms 63020 KB Output is correct
60 Correct 29 ms 63052 KB Output is correct
61 Correct 28 ms 62968 KB Output is correct
62 Correct 28 ms 62932 KB Output is correct
63 Correct 28 ms 63060 KB Output is correct
64 Correct 29 ms 62920 KB Output is correct
65 Correct 34 ms 63568 KB Output is correct
66 Correct 33 ms 63580 KB Output is correct
67 Correct 32 ms 63496 KB Output is correct
68 Correct 31 ms 63644 KB Output is correct
69 Correct 31 ms 63572 KB Output is correct
70 Correct 30 ms 63572 KB Output is correct
71 Correct 29 ms 63128 KB Output is correct
72 Correct 29 ms 63052 KB Output is correct
73 Correct 31 ms 63472 KB Output is correct
74 Correct 33 ms 63588 KB Output is correct

Subtask #3
76.0 / 76.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 62880 KB Output is correct
2 Correct 28 ms 62856 KB Output is correct
3 Correct 31 ms 62968 KB Output is correct
4 Correct 31 ms 62876 KB Output is correct
5 Correct 30 ms 62936 KB Output is correct
6 Correct 29 ms 62924 KB Output is correct
7 Correct 28 ms 62960 KB Output is correct
8 Correct 29 ms 62932 KB Output is correct
9 Correct 29 ms 62952 KB Output is correct
10 Correct 28 ms 62904 KB Output is correct
11 Correct 28 ms 62888 KB Output is correct
12 Correct 30 ms 63060 KB Output is correct
13 Correct 30 ms 62884 KB Output is correct
14 Correct 30 ms 63080 KB Output is correct
15 Correct 29 ms 62976 KB Output is correct
16 Correct 31 ms 62936 KB Output is correct
17 Correct 29 ms 62924 KB Output is correct
18 Correct 29 ms 62860 KB Output is correct
19 Correct 28 ms 62932 KB Output is correct
20 Correct 28 ms 62932 KB Output is correct
21 Correct 28 ms 62948 KB Output is correct
22 Correct 28 ms 62864 KB Output is correct
23 Correct 29 ms 62884 KB Output is correct
24 Correct 30 ms 62948 KB Output is correct
25 Correct 28 ms 62972 KB Output is correct
26 Correct 28 ms 62948 KB Output is correct
27 Correct 29 ms 62932 KB Output is correct
28 Correct 29 ms 62928 KB Output is correct
29 Correct 32 ms 62888 KB Output is correct
30 Correct 30 ms 62924 KB Output is correct
31 Correct 29 ms 62932 KB Output is correct
32 Correct 27 ms 62908 KB Output is correct
33 Correct 28 ms 62968 KB Output is correct
34 Correct 32 ms 62848 KB Output is correct
35 Correct 28 ms 62932 KB Output is correct
36 Correct 29 ms 62956 KB Output is correct
37 Correct 29 ms 62984 KB Output is correct
38 Correct 31 ms 63444 KB Output is correct
39 Correct 30 ms 63564 KB Output is correct
40 Correct 29 ms 63436 KB Output is correct
41 Correct 29 ms 63492 KB Output is correct
42 Correct 31 ms 63516 KB Output is correct
43 Correct 34 ms 63380 KB Output is correct
44 Correct 30 ms 63436 KB Output is correct
45 Correct 31 ms 63572 KB Output is correct
46 Correct 32 ms 63572 KB Output is correct
47 Correct 33 ms 63516 KB Output is correct
48 Correct 31 ms 63508 KB Output is correct
49 Correct 33 ms 63568 KB Output is correct
50 Correct 30 ms 63444 KB Output is correct
51 Correct 31 ms 63532 KB Output is correct
52 Correct 30 ms 63444 KB Output is correct
53 Correct 30 ms 63444 KB Output is correct
54 Correct 31 ms 63492 KB Output is correct
55 Correct 30 ms 63532 KB Output is correct
56 Correct 30 ms 63544 KB Output is correct
57 Correct 29 ms 63444 KB Output is correct
58 Correct 29 ms 63536 KB Output is correct
59 Correct 29 ms 63020 KB Output is correct
60 Correct 29 ms 63052 KB Output is correct
61 Correct 28 ms 62968 KB Output is correct
62 Correct 28 ms 62932 KB Output is correct
63 Correct 28 ms 63060 KB Output is correct
64 Correct 29 ms 62920 KB Output is correct
65 Correct 34 ms 63568 KB Output is correct
66 Correct 33 ms 63580 KB Output is correct
67 Correct 32 ms 63496 KB Output is correct
68 Correct 31 ms 63644 KB Output is correct
69 Correct 31 ms 63572 KB Output is correct
70 Correct 30 ms 63572 KB Output is correct
71 Correct 29 ms 63128 KB Output is correct
72 Correct 29 ms 63052 KB Output is correct
73 Correct 31 ms 63472 KB Output is correct
74 Correct 33 ms 63588 KB Output is correct
75 Correct 472 ms 144304 KB Output is correct
76 Correct 485 ms 146484 KB Output is correct
77 Correct 418 ms 148064 KB Output is correct
78 Correct 431 ms 148920 KB Output is correct
79 Correct 233 ms 148172 KB Output is correct
80 Correct 243 ms 146712 KB Output is correct
81 Correct 281 ms 128164 KB Output is correct
82 Correct 364 ms 132828 KB Output is correct
83 Correct 308 ms 130512 KB Output is correct
84 Correct 330 ms 131544 KB Output is correct
85 Correct 284 ms 128664 KB Output is correct
86 Correct 210 ms 124360 KB Output is correct
87 Correct 217 ms 124540 KB Output is correct
88 Correct 257 ms 126440 KB Output is correct
89 Correct 251 ms 126848 KB Output is correct
90 Correct 223 ms 125956 KB Output is correct
91 Correct 175 ms 122200 KB Output is correct
92 Correct 180 ms 122496 KB Output is correct
93 Correct 187 ms 123936 KB Output is correct
94 Correct 169 ms 123872 KB Output is correct
95 Correct 212 ms 125540 KB Output is correct
96 Correct 74 ms 70936 KB Output is correct
97 Correct 79 ms 71488 KB Output is correct
98 Correct 77 ms 71372 KB Output is correct
99 Correct 75 ms 71372 KB Output is correct
100 Correct 74 ms 70752 KB Output is correct
101 Correct 72 ms 70732 KB Output is correct
102 Correct 209 ms 114308 KB Output is correct
103 Correct 201 ms 114196 KB Output is correct
104 Correct 228 ms 118132 KB Output is correct
105 Correct 185 ms 113600 KB Output is correct
106 Correct 183 ms 114836 KB Output is correct
107 Correct 167 ms 111756 KB Output is correct
108 Correct 416 ms 148168 KB Output is correct
109 Correct 382 ms 151856 KB Output is correct
110 Correct 84 ms 81380 KB Output is correct
111 Correct 93 ms 81948 KB Output is correct
112 Correct 423 ms 144680 KB Output is correct
113 Correct 242 ms 151348 KB Output is correct