Submission #892148

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
892148	2023-12-25 01:42:36	box	Cake 3 (JOI19_cake3)	C++17	100 / 100	2184 ms	16964 KiB

cake3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;
const int N = 2e5, N_ = 1 << 18;
const i64 INF = 1e18;
int n, m;
int v[N], c[N], order[N];
vector<int> vv;
i64 best[N];
struct {
    i64 sum[N_ * 2]; int cnt[N_ * 2];
    void inc(int i, int x) {
        i += N_;
        sum[i] += x * vv[i - N_];
        cnt[i] += x;
        while (i /= 2) sum[i] = sum[i * 2] + sum[i * 2 + 1], cnt[i] = cnt[i * 2] + cnt[i * 2 + 1];
    }
    i64 qry(int x) {
        int i = 1;
        i64 s = 0;
        assert(m <= cnt[1]);
        while (i < N_) {
            if (cnt[i * 2 + 1] <= x) {
                x -= cnt[i * 2 + 1];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 5 / 5
• Subtask 2: 19 / 19
• Subtask 3: 76 / 76