| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 738475 |
2023-05-08T20:09:28 Z |
JakobZorz |
Stove (JOI18_stove) |
C++14 |
|
20 ms |
2440 KB |
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <stack>
#include <limits.h>
#define ll long long
using namespace std;
const int MOD = 1e9 + 7;
//#define SEGTREE
//#define TREE
//#define DSU
#ifdef SEGTREE
template<class Type>
class SegmentTree {
Type (*func)(Type a, Type b);
vector<Type> nodes;
vector<int> l;
vector<int> r;
int size_log2;
Type neutral;
void init_node(int node) {
if(node >= (1 << size_log2))
return;
l[2 * node] = l[node];
r[2 * node] = (l[node] + r[node]) / 2;
init_node(2 * node);
l[2 * node + 1] = (l[node] + r[node]) / 2;
r[2 * node + 1] = r[node];
init_node(2 * node + 1);
nodes[node] = func(nodes[2 * node], nodes[2 * node + 1]);
}
void update_node(int node) {
if(node < (1 << size_log2))
nodes[node] = func(nodes[2 * node], nodes[2 * node + 1]);
if(node != 1)
update_node(node / 2);
}
Type get(int node, int ll_, int rr) {
if(rr <= l[node] || ll_ >= r[node])
return neutral;
if(ll_ <= l[node] && rr >= r[node])
return nodes[node];
Type left = get(2 * node, ll_, rr);
Type right = get(2 * node + 1, ll_, rr);
return func(left, right);
}
public:
SegmentTree(Type (*func)(Type a, Type b), vector<Type> vector, Type neutral) : func(func), neutral(neutral) {
size_log2 = 0;
while((1 << size_log2) < vector.size())
size_log2++;
nodes.resize((1 << size_log2) * 2);
l.resize((1 << size_log2) * 2);
r.resize((1 << size_log2) * 2);
for(int i = 0; i < vector.size(); i++)
nodes[(1 << size_log2) + i] = vector[i];
l[1] = 0;
r[1] = 1 << size_log2;
init_node(1);
}
void set(int idx, Type el) {
nodes[(1 << size_log2) + idx] = el;
update_node((1 << size_log2) + idx);
}
Type get(int l, int r) {
return get(1, l, r);
}
Type get(int idx) {
return nodes[(1 << size_log2) + idx];
}
Type get() {
return nodes[1];
}
int get_first_larger_or_eq_than(int bound) {
return get_first_larger_or_eq_than(1, bound);
}
int get_first_larger_or_eq_than(int node, int bound) {
if(node >= (1 << size_log2)) {
return node - (1 << size_log2);
}
if(nodes[node * 2] > bound)
return get_first_larger_or_eq_than(node * 2, bound);
else
return get_first_larger_or_eq_than(node * 2 + 1, bound - nodes[node * 2]);
}
};
#endif
#ifdef TREE
#define POW 18
struct Node {
int parents[POW];
vector<int> conns;
int depth;
int value;
int subtree_depth;
int subtree_size;
int euler;
};
ll add(ll a, ll b) {
return a + b;
}
SegmentTree<ll> euler_path(add, vector<ll>(200001, 0), 0);
Node nodes[200000];
int n;
int setup(int node, int depth, int euler, ll dist) {
dist += nodes[node].value;
nodes[node].depth = depth;
euler_path.set(euler, euler_path.get(euler) + dist);
euler_path.set(euler + 1, euler_path.get(euler + 1) - dist);
nodes[node].euler = euler++;
for(int i = 1; i < POW; i++) {
nodes[node].parents[i] = nodes[nodes[node].parents[i - 1]].parents[i - 1];
}
int size = 1;
for(int i = 0; i < nodes[node].conns.size(); i++) {
int child = nodes[node].conns[i];
if(child != nodes[node].parents[0]) {
nodes[child].parents[0] = node;
euler = setup(child, depth + 1, euler, dist);
size += nodes[child].subtree_size;
}
}
nodes[node].subtree_size = size;
return euler;
}
void setup_tree(int root) {
nodes[root].parents[0] = root;
setup(root, 0, 0, 0);
}
int get_subtree_depth(int node) {
if(nodes[node].subtree_depth)
return nodes[node].subtree_depth;
int max_depth = 1;
for(int child : nodes[node].conns) {
if(child == nodes[node].parents[0])
continue;
max_depth = max(max_depth, get_subtree_depth(child) + 1);
}
nodes[node].subtree_depth = max_depth;
return max_depth;
}
int get_parent(int node, int depth) {
if(depth > nodes[node].depth)
return -1;
int climber = node;
for(int i = 0; i < POW; i++) {
if(depth & (1 << i) && climber != -1)
climber = nodes[climber].parents[i];
}
return climber;
}
int lca(int a, int b) {
if(nodes[a].depth < nodes[b].depth)
swap(a, b);
a = get_parent(a, nodes[a].depth - nodes[b].depth);
if(a == b)
return a;
for(int i = POW - 1; i >= 0; i--) {
if(nodes[a].parents[i] != nodes[b].parents[i]) {
a = nodes[a].parents[i];
b = nodes[b].parents[i];
}
}
return nodes[a].parents[0];
}
#endif
#ifdef DSU
class Dsu {
vector<int> arr;
int num_sets;
public:
Dsu(int size) {
arr = vector<int>(size, -1);
num_sets = size;
}
int merge(int a, int b) {
a = get(a);
b = get(b);
if(a == b)
return a;
if(arr[a] > arr[b])
swap(a, b);
arr[a] += arr[b];
arr[b] = a;
num_sets--;
return a;
}
int get(int a) {
if(arr[a] < 0)
return a;
arr[a] = get(arr[a]);
return get(arr[a]);
}
int get_size(int a) {
return -arr[get(a)];
}
int get_num_sets() {
return num_sets;
}
};
#endif
int main() {
ios::sync_with_stdio(false);
cout.tie(NULL);
cin.tie(NULL);
int n, k;
vector<int> t;
cin >> n >> k;
k--;
while(n--) {
int a;
cin >> a;
t.push_back(a);
}
ll res = t.back() - t[0] + 1;
vector<int> diff;
for(int i = 0; i < (int)t.size() - 1; i++)
diff.push_back(t[i + 1] - t[i] - 1);
sort(diff.begin(), diff.end());
for(int i = (int)diff.size() - 1; i >= (int)diff.size() - k; i--)
res -= diff[i];
cout << res << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
320 KB |
Output is correct |
| 5 |
Correct |
1 ms |
316 KB |
Output is correct |
| 6 |
Correct |
1 ms |
316 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
320 KB |
Output is correct |
| 5 |
Correct |
1 ms |
316 KB |
Output is correct |
| 6 |
Correct |
1 ms |
316 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
356 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
320 KB |
Output is correct |
| 5 |
Correct |
1 ms |
316 KB |
Output is correct |
| 6 |
Correct |
1 ms |
316 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
356 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
332 KB |
Output is correct |
| 16 |
Correct |
17 ms |
2352 KB |
Output is correct |
| 17 |
Correct |
20 ms |
2380 KB |
Output is correct |
| 18 |
Correct |
17 ms |
2388 KB |
Output is correct |
| 19 |
Correct |
17 ms |
2384 KB |
Output is correct |
| 20 |
Correct |
17 ms |
2408 KB |
Output is correct |
| 21 |
Correct |
19 ms |
2368 KB |
Output is correct |
| 22 |
Correct |
16 ms |
2344 KB |
Output is correct |
| 23 |
Correct |
17 ms |
2388 KB |
Output is correct |
| 24 |
Correct |
17 ms |
2440 KB |
Output is correct |
