# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
588675 |
2022-07-03T20:26:08 Z |
dnass |
Wiring (IOI17_wiring) |
C++14 |
|
436 ms |
16852 KB |
#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int lld;
#define INF 1000000000000000000LL
lld xx, yy, n;
vector<pair<lld, lld> > a;
vector<lld> dp;
struct item{ //ALTERAR
lld val;
item(){
val = INF;
}
item(lld valval){
val = valval;
}
};
item merge_neut = item(8*INF); //ALTERAR
item apply_neut = item(0); //ALTERAR
item merge(item a, item b){ //ALTERAR
return a.val<b.val?a:b;
}
item apply_lazy(item x, item l, lld len){ //ALTERAR
return item(x.val+l.val);
}
item apply_lazy_pure(item x, item l){ //ALTERAR
return item(x.val+l.val);
}
item build_leaf(lld pos){ //ALTERAR
return item(0);
}
struct ST{
vector<item> st;
vector<item> lazy;
void init(){
lld sz = 1;
while(sz<n) sz*=2;
st.resize(2*sz);
lazy.resize(2*sz);
}
void build(lld v = 1, lld tl = 0, lld tr = n-1){
if(tl==tr) {
st[v] = build_leaf(tl);
lazy[v] = apply_neut;
}else{
lld tm = (tl+tr)/2;
build(2*v, tl, tm);
build(2*v+1,tm+1,tr);
st[v] = merge(st[2*v], st[2*v+1]);
lazy[v] = apply_neut;
}
}
void push(int v, int tl, int tr){
st[v] = apply_lazy(st[v], lazy[v], tr-tl+1);
if(tl!=tr){
lazy[2*v] = apply_lazy_pure(lazy[2*v], lazy[v]);
lazy[2*v+1] = apply_lazy_pure(lazy[2*v+1], lazy[v]);
}
lazy[v] = apply_neut;
}
item query(lld l, lld r, lld v = 1, lld tl=0, lld tr=n-1){
push(v, tl, tr);
if(l>r) return merge_neut;
if(l<=tl&&tr<=r){
return st[v];
}
lld tm = (tl+tr)/2;
return merge(query(l,min(r,tm),2*v, tl, tm),query(max(l, tm+1), r, 2*v+1, tm+1,tr));
}
void upd(lld l, lld r, item val, lld v=1,lld tl=0, lld tr=n-1){
push(v,tl,tr);
if(l>r) return;
if(l<=tl&&tr<=r){
lazy[v] = apply_lazy_pure(lazy[v], val);
push(v,tl,tr);
return;
}
lld tm = (tl+tr)/2;
upd(l,min(r,tm), val, 2*v, tl, tm);
upd(max(l,tm+1),r, val, 2*v+1, tm+1, tr);
st[v] = merge(st[2*v], st[2*v+1]);
}
};
ST seg;
lld min_total_length(vector<int> r, vector<int> b){
xx = (lld) r.size(); yy = (lld) b.size();
n = xx+yy;
for(lld i=0;i<xx;i++) a.push_back({r[i], 1});
for(lld i=0;i<yy;i++) a.push_back({b[i], -1});
sort(a.begin(), a.end());
a.push_back({INF, 0});
dp.resize(n+1); dp[n]=0;
lld block = 0;
lld nxt_beg = n, nxt_end = n, this_end = n;
seg.init(); seg.build();
lld sum_ai = 0;
for(lld i=n-1;i>=0;i--){
if(a[i].second!=a[i+1].second){
block++;
nxt_beg = i+1;
nxt_end = this_end;
this_end = i;
if(block==1){
dp[i] = INF/100;
continue;
}
sum_ai = 0;
for(lld j=nxt_beg;j<=nxt_end;j++){
sum_ai += a[j].first;
seg.upd(j, j, sum_ai-(j+1-nxt_beg)*a[i].first+dp[j+1]);
//printf("j: %lld seg: %lld\n", j, seg.query(j, j).val);
}
}else{
if(block==1){
dp[i] = INF;
continue;
}
lld pos_block = nxt_beg-i-1;
seg.upd(nxt_beg, nxt_beg+pos_block-1, a[nxt_beg].first-a[i].first);
seg.upd(nxt_beg+pos_block, nxt_end, a[nxt_beg-1].first-a[i].first);
}
dp[i] = seg.query(nxt_beg, nxt_end).val;
//printf("nxt_end: %lld seg: %lld\n", nxt_end, seg.query(nxt_end, nxt_end).val);
dp[i] = min(dp[i], seg.query(nxt_end, nxt_end).val-dp[nxt_end+1]+dp[nxt_end]);
}
/*
for(int i=0;i<n;i++){
printf("%lld (%lld) %lld\n", a[i].first, a[i].second, dp[i]);
}
*/
return dp[0];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
300 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 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 |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
296 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
296 KB |
Output is correct |
16 |
Correct |
1 ms |
296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
154 ms |
13216 KB |
Output is correct |
4 |
Correct |
155 ms |
13216 KB |
Output is correct |
5 |
Correct |
121 ms |
13208 KB |
Output is correct |
6 |
Correct |
207 ms |
14780 KB |
Output is correct |
7 |
Correct |
221 ms |
14780 KB |
Output is correct |
8 |
Correct |
152 ms |
14776 KB |
Output is correct |
9 |
Correct |
153 ms |
14900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
260 ms |
14780 KB |
Output is correct |
4 |
Correct |
328 ms |
16368 KB |
Output is correct |
5 |
Correct |
1 ms |
240 KB |
Output is correct |
6 |
Correct |
1 ms |
292 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
322 ms |
16704 KB |
Output is correct |
19 |
Correct |
264 ms |
16696 KB |
Output is correct |
20 |
Correct |
302 ms |
16852 KB |
Output is correct |
21 |
Correct |
260 ms |
16700 KB |
Output is correct |
22 |
Correct |
284 ms |
16788 KB |
Output is correct |
23 |
Correct |
271 ms |
16712 KB |
Output is correct |
24 |
Correct |
270 ms |
16704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
370 ms |
14776 KB |
Output is correct |
3 |
Correct |
304 ms |
14784 KB |
Output is correct |
4 |
Correct |
347 ms |
14776 KB |
Output is correct |
5 |
Correct |
298 ms |
14788 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
300 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
378 ms |
16000 KB |
Output is correct |
19 |
Correct |
386 ms |
16036 KB |
Output is correct |
20 |
Correct |
368 ms |
16040 KB |
Output is correct |
21 |
Correct |
386 ms |
16048 KB |
Output is correct |
22 |
Correct |
357 ms |
16048 KB |
Output is correct |
23 |
Correct |
339 ms |
16052 KB |
Output is correct |
24 |
Correct |
318 ms |
16040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
300 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 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 |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
296 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
296 KB |
Output is correct |
16 |
Correct |
1 ms |
296 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
154 ms |
13216 KB |
Output is correct |
20 |
Correct |
155 ms |
13216 KB |
Output is correct |
21 |
Correct |
121 ms |
13208 KB |
Output is correct |
22 |
Correct |
207 ms |
14780 KB |
Output is correct |
23 |
Correct |
221 ms |
14780 KB |
Output is correct |
24 |
Correct |
152 ms |
14776 KB |
Output is correct |
25 |
Correct |
153 ms |
14900 KB |
Output is correct |
26 |
Correct |
0 ms |
212 KB |
Output is correct |
27 |
Correct |
0 ms |
212 KB |
Output is correct |
28 |
Correct |
260 ms |
14780 KB |
Output is correct |
29 |
Correct |
328 ms |
16368 KB |
Output is correct |
30 |
Correct |
1 ms |
240 KB |
Output is correct |
31 |
Correct |
1 ms |
292 KB |
Output is correct |
32 |
Correct |
0 ms |
212 KB |
Output is correct |
33 |
Correct |
1 ms |
212 KB |
Output is correct |
34 |
Correct |
0 ms |
212 KB |
Output is correct |
35 |
Correct |
1 ms |
212 KB |
Output is correct |
36 |
Correct |
0 ms |
212 KB |
Output is correct |
37 |
Correct |
1 ms |
212 KB |
Output is correct |
38 |
Correct |
0 ms |
212 KB |
Output is correct |
39 |
Correct |
0 ms |
212 KB |
Output is correct |
40 |
Correct |
1 ms |
212 KB |
Output is correct |
41 |
Correct |
1 ms |
212 KB |
Output is correct |
42 |
Correct |
1 ms |
212 KB |
Output is correct |
43 |
Correct |
322 ms |
16704 KB |
Output is correct |
44 |
Correct |
264 ms |
16696 KB |
Output is correct |
45 |
Correct |
302 ms |
16852 KB |
Output is correct |
46 |
Correct |
260 ms |
16700 KB |
Output is correct |
47 |
Correct |
284 ms |
16788 KB |
Output is correct |
48 |
Correct |
271 ms |
16712 KB |
Output is correct |
49 |
Correct |
270 ms |
16704 KB |
Output is correct |
50 |
Correct |
0 ms |
212 KB |
Output is correct |
51 |
Correct |
370 ms |
14776 KB |
Output is correct |
52 |
Correct |
304 ms |
14784 KB |
Output is correct |
53 |
Correct |
347 ms |
14776 KB |
Output is correct |
54 |
Correct |
298 ms |
14788 KB |
Output is correct |
55 |
Correct |
0 ms |
212 KB |
Output is correct |
56 |
Correct |
0 ms |
212 KB |
Output is correct |
57 |
Correct |
1 ms |
212 KB |
Output is correct |
58 |
Correct |
0 ms |
212 KB |
Output is correct |
59 |
Correct |
1 ms |
212 KB |
Output is correct |
60 |
Correct |
0 ms |
212 KB |
Output is correct |
61 |
Correct |
1 ms |
212 KB |
Output is correct |
62 |
Correct |
1 ms |
300 KB |
Output is correct |
63 |
Correct |
0 ms |
212 KB |
Output is correct |
64 |
Correct |
1 ms |
212 KB |
Output is correct |
65 |
Correct |
1 ms |
212 KB |
Output is correct |
66 |
Correct |
1 ms |
212 KB |
Output is correct |
67 |
Correct |
378 ms |
16000 KB |
Output is correct |
68 |
Correct |
386 ms |
16036 KB |
Output is correct |
69 |
Correct |
368 ms |
16040 KB |
Output is correct |
70 |
Correct |
386 ms |
16048 KB |
Output is correct |
71 |
Correct |
357 ms |
16048 KB |
Output is correct |
72 |
Correct |
339 ms |
16052 KB |
Output is correct |
73 |
Correct |
318 ms |
16040 KB |
Output is correct |
74 |
Correct |
350 ms |
16684 KB |
Output is correct |
75 |
Correct |
334 ms |
16348 KB |
Output is correct |
76 |
Correct |
349 ms |
16716 KB |
Output is correct |
77 |
Correct |
393 ms |
16188 KB |
Output is correct |
78 |
Correct |
381 ms |
16216 KB |
Output is correct |
79 |
Correct |
365 ms |
16132 KB |
Output is correct |
80 |
Correct |
351 ms |
16028 KB |
Output is correct |
81 |
Correct |
300 ms |
16220 KB |
Output is correct |
82 |
Correct |
323 ms |
16180 KB |
Output is correct |
83 |
Correct |
261 ms |
16360 KB |
Output is correct |
84 |
Correct |
271 ms |
16696 KB |
Output is correct |
85 |
Correct |
366 ms |
16712 KB |
Output is correct |
86 |
Correct |
338 ms |
16712 KB |
Output is correct |
87 |
Correct |
313 ms |
16820 KB |
Output is correct |
88 |
Correct |
385 ms |
16712 KB |
Output is correct |
89 |
Correct |
382 ms |
16720 KB |
Output is correct |
90 |
Correct |
388 ms |
16784 KB |
Output is correct |
91 |
Correct |
343 ms |
16724 KB |
Output is correct |
92 |
Correct |
383 ms |
16712 KB |
Output is correct |
93 |
Correct |
375 ms |
16668 KB |
Output is correct |
94 |
Correct |
362 ms |
16716 KB |
Output is correct |
95 |
Correct |
436 ms |
16720 KB |
Output is correct |
96 |
Correct |
306 ms |
16716 KB |
Output is correct |
97 |
Correct |
373 ms |
16704 KB |
Output is correct |
98 |
Correct |
342 ms |
16712 KB |
Output is correct |
99 |
Correct |
346 ms |
16712 KB |
Output is correct |
100 |
Correct |
396 ms |
16712 KB |
Output is correct |
101 |
Correct |
335 ms |
16716 KB |
Output is correct |
102 |
Correct |
358 ms |
16716 KB |
Output is correct |