# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
165137 |
2019-11-25T10:32:27 Z |
Segtree |
Wiring (IOI17_wiring) |
C++14 |
|
289 ms |
58384 KB |
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include"wiring.h"
using namespace std;
typedef long long ll;
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define mod 1000000007
#define mad(a,b) a=(a+b)%mod
#define N 100010
struct qry{
ll ida,idb,cost;
bool operator<(const qry&key)const{
if(this->ida!=key.ida)return this->ida>key.ida;
if(this->idb!=key.idb)return this->idb>key.idb;
return this->cost>key.cost;
};
};
qry qrys(ll p,ll q,ll r){
qry gen;
gen.ida=p;
gen.idb=q;
gen.cost=r;
return gen;
}
priority_queue<qry> Q;
unordered_map<ll,ll> dist[N];
unordered_set<ll> ava[N];
void ad(ll x,ll y){
ava[x].insert(y);
}
bool av(ll x,ll y){
return ava[x].find(y)!=ava[x].end();
}
ll lastsc[2*N];
ll lastchi[2*N],lastchj[2*N];
ll ruia[N],ruib[N];
ll min_total_length(vector<int> a,vector<int> b){
ruia[0]=0; for(int i=0;i<a.size();i++)ruia[i+1]=ruia[i]+a[i];
ruib[0]=0; for(int i=0;i<b.size();i++)ruib[i+1]=ruib[i]+b[i];
for(int i=0;i<2*N;i++){
lastsc[i]=1e17;
lastchi[i]=0;
lastchj[i]=0;
}
Q.push(qrys(0,0,0));
ad(a.size()-1,b.size()-1);
ll q=0;
for(int p=0;p<a.size();p++){
for(;q<b.size()&&a[p]>b[q];q++){}
if(q-1>=0)ad(p,q-1);
if(q<b.size())ad(p,q);
//cout<<"$"<<p<<" "<<q<<endl;
}
q=0;
for(int p=0;p<b.size();p++){
for(;q<a.size()&&b[p]>a[q];q++){}
if(q-1>=0)ad(q-1,p);
if(q<a.size())ad(q,p);
//cout<<"$"<<p<<" "<<q<<endl;
}
/*
for(int i=0;i<a.size();i++)for(int j=0;j<b.size();j++){
if(av(i,j))cout<<"#"<<i<<" "<<j<<endl;
}*/
while(!Q.empty()){
ll i=Q.top().ida;
ll j=Q.top().idb;
ll cost=Q.top().cost+abs(a[i]-b[j]);
Q.pop();
if(av(i,j)==0)continue;
if(dist[i].find(j)!=dist[i].end()){
if(dist[i][j]<=cost)continue;
}
ll base=i-j+N;
ll ch=lastsc[base]+abs(ruia[i+1]-ruia[lastchi[base]+1]-(ruib[j+1]-ruib[lastchj[base]+1]));
chmin(cost,ch);
lastsc[base]=cost;
lastchi[base]=i,lastchj[base]=j;
if(i+1<a.size()){
Q.push(qrys(i+1,j,cost));
}
if(j+1<b.size()){
Q.push(qrys(i,j+1,cost));
}
//cout<<"dist:"<<i<<" "<<j<<" "<<cost<<endl;
dist[i][j]=cost;
}
return dist[a.size()-1][b.size()-1];
}/*
int main(){
cin.tie(0);
ios::sync_with_stdio(0);
vector<ll> a,b;
ll n,m; cin>>n>>m;
for(int i=0;i<n;i++){
ll x; cin>>x;
a.push_back(x);
}
for(int i=0;i<m;i++){
ll x; cin>>x;
b.push_back(x);
}
cout<<min_total_length(a,b)<<endl;
}*/
Compilation message
wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:44:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
ruia[0]=0; for(int i=0;i<a.size();i++)ruia[i+1]=ruia[i]+a[i];
~^~~~~~~~~
wiring.cpp:45:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
ruib[0]=0; for(int i=0;i<b.size();i++)ruib[i+1]=ruib[i]+b[i];
~^~~~~~~~~
wiring.cpp:54:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int p=0;p<a.size();p++){
~^~~~~~~~~
wiring.cpp:55:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(;q<b.size()&&a[p]>b[q];q++){}
~^~~~~~~~~
wiring.cpp:57:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(q<b.size())ad(p,q);
~^~~~~~~~~
wiring.cpp:61:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int p=0;p<b.size();p++){
~^~~~~~~~~
wiring.cpp:62:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(;q<a.size()&&b[p]>a[q];q++){}
~^~~~~~~~~
wiring.cpp:64:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(q<a.size())ad(q,p);
~^~~~~~~~~
wiring.cpp:86:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i+1<a.size()){
~~~^~~~~~~~~
wiring.cpp:89:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(j+1<b.size()){
~~~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
15992 KB |
Output is correct |
2 |
Correct |
18 ms |
15992 KB |
Output is correct |
3 |
Correct |
18 ms |
15992 KB |
Output is correct |
4 |
Correct |
18 ms |
15992 KB |
Output is correct |
5 |
Correct |
18 ms |
15992 KB |
Output is correct |
6 |
Correct |
18 ms |
15992 KB |
Output is correct |
7 |
Correct |
18 ms |
15992 KB |
Output is correct |
8 |
Correct |
18 ms |
15992 KB |
Output is correct |
9 |
Correct |
18 ms |
16120 KB |
Output is correct |
10 |
Correct |
19 ms |
16120 KB |
Output is correct |
11 |
Correct |
24 ms |
16120 KB |
Output is correct |
12 |
Correct |
18 ms |
16120 KB |
Output is correct |
13 |
Correct |
18 ms |
16092 KB |
Output is correct |
14 |
Correct |
19 ms |
16124 KB |
Output is correct |
15 |
Correct |
18 ms |
16120 KB |
Output is correct |
16 |
Correct |
20 ms |
16120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
15992 KB |
Output is correct |
2 |
Correct |
18 ms |
15996 KB |
Output is correct |
3 |
Correct |
114 ms |
35352 KB |
Output is correct |
4 |
Correct |
111 ms |
35496 KB |
Output is correct |
5 |
Correct |
104 ms |
33196 KB |
Output is correct |
6 |
Correct |
138 ms |
40172 KB |
Output is correct |
7 |
Correct |
137 ms |
40328 KB |
Output is correct |
8 |
Correct |
142 ms |
40216 KB |
Output is correct |
9 |
Correct |
150 ms |
40320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
15992 KB |
Output is correct |
2 |
Correct |
18 ms |
15992 KB |
Output is correct |
3 |
Correct |
232 ms |
51992 KB |
Output is correct |
4 |
Correct |
231 ms |
57208 KB |
Output is correct |
5 |
Correct |
18 ms |
15964 KB |
Output is correct |
6 |
Correct |
19 ms |
15968 KB |
Output is correct |
7 |
Correct |
18 ms |
15996 KB |
Output is correct |
8 |
Correct |
17 ms |
15992 KB |
Output is correct |
9 |
Correct |
18 ms |
15996 KB |
Output is correct |
10 |
Correct |
17 ms |
15992 KB |
Output is correct |
11 |
Correct |
18 ms |
15992 KB |
Output is correct |
12 |
Correct |
18 ms |
15992 KB |
Output is correct |
13 |
Correct |
17 ms |
15992 KB |
Output is correct |
14 |
Correct |
17 ms |
15992 KB |
Output is correct |
15 |
Correct |
18 ms |
15992 KB |
Output is correct |
16 |
Correct |
18 ms |
15992 KB |
Output is correct |
17 |
Correct |
18 ms |
16120 KB |
Output is correct |
18 |
Correct |
218 ms |
53116 KB |
Output is correct |
19 |
Correct |
263 ms |
53280 KB |
Output is correct |
20 |
Correct |
238 ms |
57720 KB |
Output is correct |
21 |
Correct |
221 ms |
53112 KB |
Output is correct |
22 |
Correct |
226 ms |
54008 KB |
Output is correct |
23 |
Correct |
246 ms |
53880 KB |
Output is correct |
24 |
Correct |
230 ms |
54024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
15992 KB |
Output is correct |
2 |
Correct |
259 ms |
55584 KB |
Output is correct |
3 |
Correct |
269 ms |
55544 KB |
Output is correct |
4 |
Correct |
241 ms |
55928 KB |
Output is correct |
5 |
Correct |
247 ms |
55664 KB |
Output is correct |
6 |
Correct |
21 ms |
15992 KB |
Output is correct |
7 |
Correct |
20 ms |
15996 KB |
Output is correct |
8 |
Correct |
18 ms |
15992 KB |
Output is correct |
9 |
Correct |
18 ms |
15992 KB |
Output is correct |
10 |
Correct |
19 ms |
15992 KB |
Output is correct |
11 |
Correct |
18 ms |
15992 KB |
Output is correct |
12 |
Correct |
17 ms |
15992 KB |
Output is correct |
13 |
Correct |
18 ms |
15992 KB |
Output is correct |
14 |
Correct |
19 ms |
15992 KB |
Output is correct |
15 |
Correct |
18 ms |
15992 KB |
Output is correct |
16 |
Correct |
18 ms |
15992 KB |
Output is correct |
17 |
Correct |
18 ms |
15992 KB |
Output is correct |
18 |
Correct |
239 ms |
52688 KB |
Output is correct |
19 |
Correct |
241 ms |
56568 KB |
Output is correct |
20 |
Correct |
251 ms |
56088 KB |
Output is correct |
21 |
Correct |
260 ms |
55216 KB |
Output is correct |
22 |
Correct |
238 ms |
52752 KB |
Output is correct |
23 |
Correct |
196 ms |
48124 KB |
Output is correct |
24 |
Correct |
220 ms |
50880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
15992 KB |
Output is correct |
2 |
Correct |
18 ms |
15992 KB |
Output is correct |
3 |
Correct |
18 ms |
15992 KB |
Output is correct |
4 |
Correct |
18 ms |
15992 KB |
Output is correct |
5 |
Correct |
18 ms |
15992 KB |
Output is correct |
6 |
Correct |
18 ms |
15992 KB |
Output is correct |
7 |
Correct |
18 ms |
15992 KB |
Output is correct |
8 |
Correct |
18 ms |
15992 KB |
Output is correct |
9 |
Correct |
18 ms |
16120 KB |
Output is correct |
10 |
Correct |
19 ms |
16120 KB |
Output is correct |
11 |
Correct |
24 ms |
16120 KB |
Output is correct |
12 |
Correct |
18 ms |
16120 KB |
Output is correct |
13 |
Correct |
18 ms |
16092 KB |
Output is correct |
14 |
Correct |
19 ms |
16124 KB |
Output is correct |
15 |
Correct |
18 ms |
16120 KB |
Output is correct |
16 |
Correct |
20 ms |
16120 KB |
Output is correct |
17 |
Correct |
18 ms |
15992 KB |
Output is correct |
18 |
Correct |
18 ms |
15996 KB |
Output is correct |
19 |
Correct |
114 ms |
35352 KB |
Output is correct |
20 |
Correct |
111 ms |
35496 KB |
Output is correct |
21 |
Correct |
104 ms |
33196 KB |
Output is correct |
22 |
Correct |
138 ms |
40172 KB |
Output is correct |
23 |
Correct |
137 ms |
40328 KB |
Output is correct |
24 |
Correct |
142 ms |
40216 KB |
Output is correct |
25 |
Correct |
150 ms |
40320 KB |
Output is correct |
26 |
Correct |
18 ms |
15992 KB |
Output is correct |
27 |
Correct |
18 ms |
15992 KB |
Output is correct |
28 |
Correct |
232 ms |
51992 KB |
Output is correct |
29 |
Correct |
231 ms |
57208 KB |
Output is correct |
30 |
Correct |
18 ms |
15964 KB |
Output is correct |
31 |
Correct |
19 ms |
15968 KB |
Output is correct |
32 |
Correct |
18 ms |
15996 KB |
Output is correct |
33 |
Correct |
17 ms |
15992 KB |
Output is correct |
34 |
Correct |
18 ms |
15996 KB |
Output is correct |
35 |
Correct |
17 ms |
15992 KB |
Output is correct |
36 |
Correct |
18 ms |
15992 KB |
Output is correct |
37 |
Correct |
18 ms |
15992 KB |
Output is correct |
38 |
Correct |
17 ms |
15992 KB |
Output is correct |
39 |
Correct |
17 ms |
15992 KB |
Output is correct |
40 |
Correct |
18 ms |
15992 KB |
Output is correct |
41 |
Correct |
18 ms |
15992 KB |
Output is correct |
42 |
Correct |
18 ms |
16120 KB |
Output is correct |
43 |
Correct |
218 ms |
53116 KB |
Output is correct |
44 |
Correct |
263 ms |
53280 KB |
Output is correct |
45 |
Correct |
238 ms |
57720 KB |
Output is correct |
46 |
Correct |
221 ms |
53112 KB |
Output is correct |
47 |
Correct |
226 ms |
54008 KB |
Output is correct |
48 |
Correct |
246 ms |
53880 KB |
Output is correct |
49 |
Correct |
230 ms |
54024 KB |
Output is correct |
50 |
Correct |
17 ms |
15992 KB |
Output is correct |
51 |
Correct |
259 ms |
55584 KB |
Output is correct |
52 |
Correct |
269 ms |
55544 KB |
Output is correct |
53 |
Correct |
241 ms |
55928 KB |
Output is correct |
54 |
Correct |
247 ms |
55664 KB |
Output is correct |
55 |
Correct |
21 ms |
15992 KB |
Output is correct |
56 |
Correct |
20 ms |
15996 KB |
Output is correct |
57 |
Correct |
18 ms |
15992 KB |
Output is correct |
58 |
Correct |
18 ms |
15992 KB |
Output is correct |
59 |
Correct |
19 ms |
15992 KB |
Output is correct |
60 |
Correct |
18 ms |
15992 KB |
Output is correct |
61 |
Correct |
17 ms |
15992 KB |
Output is correct |
62 |
Correct |
18 ms |
15992 KB |
Output is correct |
63 |
Correct |
19 ms |
15992 KB |
Output is correct |
64 |
Correct |
18 ms |
15992 KB |
Output is correct |
65 |
Correct |
18 ms |
15992 KB |
Output is correct |
66 |
Correct |
18 ms |
15992 KB |
Output is correct |
67 |
Correct |
239 ms |
52688 KB |
Output is correct |
68 |
Correct |
241 ms |
56568 KB |
Output is correct |
69 |
Correct |
251 ms |
56088 KB |
Output is correct |
70 |
Correct |
260 ms |
55216 KB |
Output is correct |
71 |
Correct |
238 ms |
52752 KB |
Output is correct |
72 |
Correct |
196 ms |
48124 KB |
Output is correct |
73 |
Correct |
220 ms |
50880 KB |
Output is correct |
74 |
Correct |
262 ms |
53168 KB |
Output is correct |
75 |
Correct |
263 ms |
54804 KB |
Output is correct |
76 |
Correct |
252 ms |
53456 KB |
Output is correct |
77 |
Correct |
275 ms |
55332 KB |
Output is correct |
78 |
Correct |
243 ms |
53380 KB |
Output is correct |
79 |
Correct |
268 ms |
57108 KB |
Output is correct |
80 |
Correct |
266 ms |
51920 KB |
Output is correct |
81 |
Correct |
251 ms |
52112 KB |
Output is correct |
82 |
Correct |
201 ms |
49792 KB |
Output is correct |
83 |
Correct |
185 ms |
47444 KB |
Output is correct |
84 |
Correct |
193 ms |
46732 KB |
Output is correct |
85 |
Correct |
262 ms |
55116 KB |
Output is correct |
86 |
Correct |
236 ms |
52428 KB |
Output is correct |
87 |
Correct |
215 ms |
50432 KB |
Output is correct |
88 |
Correct |
263 ms |
54220 KB |
Output is correct |
89 |
Correct |
266 ms |
55572 KB |
Output is correct |
90 |
Correct |
260 ms |
54224 KB |
Output is correct |
91 |
Correct |
218 ms |
51200 KB |
Output is correct |
92 |
Correct |
280 ms |
56884 KB |
Output is correct |
93 |
Correct |
250 ms |
54292 KB |
Output is correct |
94 |
Correct |
289 ms |
56848 KB |
Output is correct |
95 |
Correct |
279 ms |
58192 KB |
Output is correct |
96 |
Correct |
218 ms |
50964 KB |
Output is correct |
97 |
Correct |
224 ms |
51408 KB |
Output is correct |
98 |
Correct |
233 ms |
52544 KB |
Output is correct |
99 |
Correct |
227 ms |
52472 KB |
Output is correct |
100 |
Correct |
278 ms |
58384 KB |
Output is correct |
101 |
Correct |
253 ms |
53292 KB |
Output is correct |
102 |
Correct |
248 ms |
52816 KB |
Output is correct |