oj.uz

Submission #625471

# Submission time Handle Problem Language Result Execution time Memory
625471 2022-08-10T12:10:13 Z Do_you_copy Cake 3 (JOI19_cake3) C++17
100 / 100
 572 ms 151228 KB 
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using ull = unsigned ll;
using ld = long double;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

//const ll Mod = 1000000007;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 2e5 + 10;
int n, m;
int node_cnt = 1;

vector <int> val[maxN * 4];
vector <ll> sum[maxN * 4];
vector <int> b;
ll pre[maxN];

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 maxx = l;
    int minn = 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) maxx = max(maxx, *it);
        else minn = min(minn, *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, maxx);
    build(wt[id].rp, p, j, minn, r);
}

ll get(int k, int i, int j){
    bool flag = 0; if (k == 3 && i == 2 && j == 5) flag = 1;
    if (k == 0) return 0;
    --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;
}

struct TCake{
    int v, c;
    bool operator < (const TCake &other) const{
        return c < other.c;
    }
};
TCake a[maxN];

ll ans = -1e15;

//IOI 2014 Holiday?
void DnC(int l, int r, int from, int to){
    if (l > r) return;
    int mid = (l + r) / 2;
    ll tem = -1e15, pos = 0;
    for (int i = max(from, mid + m - 1) ; i <= to; ++i){
        ll q = - get(m, mid, i) + 2 * (a[mid].c - a[i].c);
        if (tem < q){
            pos = i;
            tem = q;
        }
    }
    ans = max(ans, tem);
    assert(pos != 0);
	DnC(l, mid - 1, from, pos);
	DnC(mid + 1, r, pos, to);
}

void Init(){
    cin >> n >> m;
    for (int i = 1; i <= n; ++i){
        cin >> a[i].v >> a[i].c;
    }
    sort(a + 1, a + n + 1);
    b.resize(n + 1);
    for (int i = 1; i <= n; ++i){
        b[i] = -a[i].v;
    }
    build(1, b.begin() + 1, b.end(), *min_element(b.begin() + 1, b.end()),
           *max_element(b.begin() + 1, b.end()));
    DnC(1, n - m + 1, m, n);
    cout << ans;
}

#define debu
#define taskname "test"
signed main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        #ifdef debug
        freopen(taskname".out", "w", stdout);
        #endif
    }
    faster;
    ll tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
    if (fopen("timeout.txt", "r")){
        ofstream timeout("timeout.txt");
        timeout << 1000 * double(clock()) / CLOCKS_PER_SEC;
        #ifndef debug
        cerr << "\nTime elapsed: " << 1000 * double(clock()) / CLOCKS_PER_SEC << "ms\n";
        #endif
    }
}

Compilation message

cake3.cpp:50:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   50 | void build(int id, auto i, auto j, int l, int r){
      |                    ^~~~
cake3.cpp:50:28: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   50 | 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:84:13: warning: unused variable 'mid' [-Wunused-variable]
   84 |         int mid = (l + r) / 2;
      |             ^~~
cake3.cpp:77:10: warning: variable 'flag' set but not used [-Wunused-but-set-variable]
   77 |     bool flag = 0; if (k == 3 && i == 2 && j == 5) flag = 1;
      |          ^~~~
cake3.cpp: In function 'int main()':
cake3.cpp:151:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 62940 KB Output is correct
2 Correct 30 ms 62888 KB Output is correct
3 Correct 31 ms 62932 KB Output is correct
4 Correct 31 ms 62924 KB Output is correct
5 Correct 30 ms 62920 KB Output is correct
6 Correct 32 ms 62972 KB Output is correct
7 Correct 30 ms 62900 KB Output is correct
8 Correct 28 ms 62952 KB Output is correct
9 Correct 44 ms 62920 KB Output is correct
10 Correct 35 ms 62860 KB Output is correct
11 Correct 35 ms 62912 KB Output is correct
12 Correct 33 ms 62928 KB Output is correct
13 Correct 36 ms 62864 KB Output is correct
14 Correct 37 ms 62932 KB Output is correct
15 Correct 72 ms 62960 KB Output is correct
16 Correct 30 ms 62948 KB Output is correct
17 Correct 39 ms 62860 KB Output is correct
18 Correct 37 ms 62988 KB Output is correct
19 Correct 38 ms 62924 KB Output is correct
20 Correct 41 ms 62912 KB Output is correct
21 Correct 42 ms 62924 KB Output is correct
22 Correct 29 ms 62972 KB Output is correct
23 Correct 32 ms 62920 KB Output is correct
24 Correct 32 ms 62916 KB Output is correct
25 Correct 28 ms 62896 KB Output is correct
26 Correct 38 ms 62880 KB Output is correct
27 Correct 39 ms 62868 KB Output is correct
28 Correct 35 ms 62940 KB Output is correct
29 Correct 37 ms 62860 KB Output is correct
30 Correct 42 ms 62956 KB Output is correct
31 Correct 32 ms 62860 KB Output is correct
32 Correct 39 ms 62900 KB Output is correct
33 Correct 32 ms 62932 KB Output is correct
34 Correct 31 ms 62900 KB Output is correct
35 Correct 28 ms 62904 KB Output is correct
36 Correct 35 ms 62988 KB Output is correct
37 Correct 34 ms 62900 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 62940 KB Output is correct
2 Correct 30 ms 62888 KB Output is correct
3 Correct 31 ms 62932 KB Output is correct
4 Correct 31 ms 62924 KB Output is correct
5 Correct 30 ms 62920 KB Output is correct
6 Correct 32 ms 62972 KB Output is correct
7 Correct 30 ms 62900 KB Output is correct
8 Correct 28 ms 62952 KB Output is correct
9 Correct 44 ms 62920 KB Output is correct
10 Correct 35 ms 62860 KB Output is correct
11 Correct 35 ms 62912 KB Output is correct
12 Correct 33 ms 62928 KB Output is correct
13 Correct 36 ms 62864 KB Output is correct
14 Correct 37 ms 62932 KB Output is correct
15 Correct 72 ms 62960 KB Output is correct
16 Correct 30 ms 62948 KB Output is correct
17 Correct 39 ms 62860 KB Output is correct
18 Correct 37 ms 62988 KB Output is correct
19 Correct 38 ms 62924 KB Output is correct
20 Correct 41 ms 62912 KB Output is correct
21 Correct 42 ms 62924 KB Output is correct
22 Correct 29 ms 62972 KB Output is correct
23 Correct 32 ms 62920 KB Output is correct
24 Correct 32 ms 62916 KB Output is correct
25 Correct 28 ms 62896 KB Output is correct
26 Correct 38 ms 62880 KB Output is correct
27 Correct 39 ms 62868 KB Output is correct
28 Correct 35 ms 62940 KB Output is correct
29 Correct 37 ms 62860 KB Output is correct
30 Correct 42 ms 62956 KB Output is correct
31 Correct 32 ms 62860 KB Output is correct
32 Correct 39 ms 62900 KB Output is correct
33 Correct 32 ms 62932 KB Output is correct
34 Correct 31 ms 62900 KB Output is correct
35 Correct 28 ms 62904 KB Output is correct
36 Correct 35 ms 62988 KB Output is correct
37 Correct 34 ms 62900 KB Output is correct
38 Correct 44 ms 63508 KB Output is correct
39 Correct 38 ms 63472 KB Output is correct
40 Correct 42 ms 63484 KB Output is correct
41 Correct 37 ms 63512 KB Output is correct
42 Correct 40 ms 63540 KB Output is correct
43 Correct 53 ms 63428 KB Output is correct
44 Correct 36 ms 63484 KB Output is correct
45 Correct 36 ms 63528 KB Output is correct
46 Correct 35 ms 63444 KB Output is correct
47 Correct 33 ms 63548 KB Output is correct
48 Correct 35 ms 63412 KB Output is correct
49 Correct 39 ms 63564 KB Output is correct
50 Correct 64 ms 63488 KB Output is correct
51 Correct 41 ms 63544 KB Output is correct
52 Correct 38 ms 63484 KB Output is correct
53 Correct 40 ms 63480 KB Output is correct
54 Correct 58 ms 63516 KB Output is correct
55 Correct 36 ms 63444 KB Output is correct
56 Correct 38 ms 63436 KB Output is correct
57 Correct 33 ms 63536 KB Output is correct
58 Correct 39 ms 63428 KB Output is correct
59 Correct 34 ms 62872 KB Output is correct
60 Correct 31 ms 63052 KB Output is correct
61 Correct 30 ms 62992 KB Output is correct
62 Correct 54 ms 62996 KB Output is correct
63 Correct 30 ms 63052 KB Output is correct
64 Correct 31 ms 62904 KB Output is correct
65 Correct 36 ms 63452 KB Output is correct
66 Correct 39 ms 63436 KB Output is correct
67 Correct 38 ms 63532 KB Output is correct
68 Correct 39 ms 63528 KB Output is correct
69 Correct 34 ms 63440 KB Output is correct
70 Correct 42 ms 63560 KB Output is correct
71 Correct 31 ms 63052 KB Output is correct
72 Correct 32 ms 63100 KB Output is correct
73 Correct 41 ms 63444 KB Output is correct
74 Correct 36 ms 63580 KB Output is correct

Subtask #3
76.0 / 76.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 62940 KB Output is correct
2 Correct 30 ms 62888 KB Output is correct
3 Correct 31 ms 62932 KB Output is correct
4 Correct 31 ms 62924 KB Output is correct
5 Correct 30 ms 62920 KB Output is correct
6 Correct 32 ms 62972 KB Output is correct
7 Correct 30 ms 62900 KB Output is correct
8 Correct 28 ms 62952 KB Output is correct
9 Correct 44 ms 62920 KB Output is correct
10 Correct 35 ms 62860 KB Output is correct
11 Correct 35 ms 62912 KB Output is correct
12 Correct 33 ms 62928 KB Output is correct
13 Correct 36 ms 62864 KB Output is correct
14 Correct 37 ms 62932 KB Output is correct
15 Correct 72 ms 62960 KB Output is correct
16 Correct 30 ms 62948 KB Output is correct
17 Correct 39 ms 62860 KB Output is correct
18 Correct 37 ms 62988 KB Output is correct
19 Correct 38 ms 62924 KB Output is correct
20 Correct 41 ms 62912 KB Output is correct
21 Correct 42 ms 62924 KB Output is correct
22 Correct 29 ms 62972 KB Output is correct
23 Correct 32 ms 62920 KB Output is correct
24 Correct 32 ms 62916 KB Output is correct
25 Correct 28 ms 62896 KB Output is correct
26 Correct 38 ms 62880 KB Output is correct
27 Correct 39 ms 62868 KB Output is correct
28 Correct 35 ms 62940 KB Output is correct
29 Correct 37 ms 62860 KB Output is correct
30 Correct 42 ms 62956 KB Output is correct
31 Correct 32 ms 62860 KB Output is correct
32 Correct 39 ms 62900 KB Output is correct
33 Correct 32 ms 62932 KB Output is correct
34 Correct 31 ms 62900 KB Output is correct
35 Correct 28 ms 62904 KB Output is correct
36 Correct 35 ms 62988 KB Output is correct
37 Correct 34 ms 62900 KB Output is correct
38 Correct 44 ms 63508 KB Output is correct
39 Correct 38 ms 63472 KB Output is correct
40 Correct 42 ms 63484 KB Output is correct
41 Correct 37 ms 63512 KB Output is correct
42 Correct 40 ms 63540 KB Output is correct
43 Correct 53 ms 63428 KB Output is correct
44 Correct 36 ms 63484 KB Output is correct
45 Correct 36 ms 63528 KB Output is correct
46 Correct 35 ms 63444 KB Output is correct
47 Correct 33 ms 63548 KB Output is correct
48 Correct 35 ms 63412 KB Output is correct
49 Correct 39 ms 63564 KB Output is correct
50 Correct 64 ms 63488 KB Output is correct
51 Correct 41 ms 63544 KB Output is correct
52 Correct 38 ms 63484 KB Output is correct
53 Correct 40 ms 63480 KB Output is correct
54 Correct 58 ms 63516 KB Output is correct
55 Correct 36 ms 63444 KB Output is correct
56 Correct 38 ms 63436 KB Output is correct
57 Correct 33 ms 63536 KB Output is correct
58 Correct 39 ms 63428 KB Output is correct
59 Correct 34 ms 62872 KB Output is correct
60 Correct 31 ms 63052 KB Output is correct
61 Correct 30 ms 62992 KB Output is correct
62 Correct 54 ms 62996 KB Output is correct
63 Correct 30 ms 63052 KB Output is correct
64 Correct 31 ms 62904 KB Output is correct
65 Correct 36 ms 63452 KB Output is correct
66 Correct 39 ms 63436 KB Output is correct
67 Correct 38 ms 63532 KB Output is correct
68 Correct 39 ms 63528 KB Output is correct
69 Correct 34 ms 63440 KB Output is correct
70 Correct 42 ms 63560 KB Output is correct
71 Correct 31 ms 63052 KB Output is correct
72 Correct 32 ms 63100 KB Output is correct
73 Correct 41 ms 63444 KB Output is correct
74 Correct 36 ms 63580 KB Output is correct
75 Correct 552 ms 143452 KB Output is correct
76 Correct 572 ms 145404 KB Output is correct
77 Correct 566 ms 147108 KB Output is correct
78 Correct 549 ms 148064 KB Output is correct
79 Correct 254 ms 148204 KB Output is correct
80 Correct 271 ms 146508 KB Output is correct
81 Correct 302 ms 127184 KB Output is correct
82 Correct 436 ms 131740 KB Output is correct
83 Correct 346 ms 129472 KB Output is correct
84 Correct 342 ms 130508 KB Output is correct
85 Correct 433 ms 127624 KB Output is correct
86 Correct 250 ms 123900 KB Output is correct
87 Correct 237 ms 123892 KB Output is correct
88 Correct 261 ms 125660 KB Output is correct
89 Correct 323 ms 126156 KB Output is correct
90 Correct 226 ms 125340 KB Output is correct
91 Correct 182 ms 121924 KB Output is correct
92 Correct 185 ms 121868 KB Output is correct
93 Correct 200 ms 123228 KB Output is correct
94 Correct 177 ms 123584 KB Output is correct
95 Correct 220 ms 124928 KB Output is correct
96 Correct 77 ms 69956 KB Output is correct
97 Correct 81 ms 70520 KB Output is correct
98 Correct 79 ms 70456 KB Output is correct
99 Correct 76 ms 70408 KB Output is correct
100 Correct 74 ms 70004 KB Output is correct
101 Correct 80 ms 70052 KB Output is correct
102 Correct 220 ms 113192 KB Output is correct
103 Correct 240 ms 113248 KB Output is correct
104 Correct 230 ms 117012 KB Output is correct
105 Correct 191 ms 112688 KB Output is correct
106 Correct 211 ms 114076 KB Output is correct
107 Correct 174 ms 111028 KB Output is correct
108 Correct 498 ms 147528 KB Output is correct
109 Correct 434 ms 151000 KB Output is correct
110 Correct 131 ms 80716 KB Output is correct
111 Correct 94 ms 80844 KB Output is correct
112 Correct 474 ms 143852 KB Output is correct
113 Correct 268 ms 151228 KB Output is correct