QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#503636 | #8806. Summer Driving | EXODUS | 25 ✓ | 3102ms | 132228kb | C++17 | 5.3kb | 2024-08-03 21:33:12 | 2024-08-03 21:33:18 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
constexpr int N=3e5+7,inf=0x3f3f3f3f;
int n,R,a,b;
vector<int>g[N];
int dep[N],dfn[N],rdfn[N],ord[N],mnv[N],omnv[N],dfx,lbd[N],rbd[N],nxt[N];
vector<int>buc[N];
priority_queue<int,vector<int>,greater<int>>q[N];
template<typename info_t,typename tag_t>struct Sgt{
#define ls(k) ((k)<<1)
#define rs(k) ((k)<<1|1)
struct node{info_t info;tag_t tag;}t[N<<2];
void apply(int k,tag_t v){t[k].info=t[k].info+v;t[k].tag=t[k].tag+v;}
void push(int k){if(t[k].tag!=tag_t())apply(ls(k),t[k].tag),apply(rs(k),t[k].tag),t[k].tag=tag_t();}
void pull(int k){t[k].info=t[ls(k)].info+t[rs(k)].info;}
void clear(){
for(int i=1;i<=4*n;i++)
t[i].info=info_t(),t[i].tag=tag_t();
}
void modify(int l,int r,int k,int ql,int qr,tag_t v){
if(ql>qr)return;
if(ql<=l&&r<=qr)return apply(k,v);
int mid=(l+r)>>1;push(k);
if(ql<=mid)modify(l,mid,ls(k),ql,qr,v);
if(mid<qr)modify(mid+1,r,rs(k),ql,qr,v);
pull(k);
}
info_t query(int l,int r,int k,int ql,int qr){
if(ql>qr)return info_t();
if(ql<=l&&r<=qr)return t[k].info;
int mid=(l+r)>>1;push(k);
info_t res=info_t();
if(ql<=mid){
if(mid<qr)res=query(l,mid,ls(k),ql,qr)+query(mid+1,r,rs(k),ql,qr);
else res=query(l,mid,ls(k),ql,qr);
}else res=query(mid+1,r,rs(k),ql,qr);
return res;
}
#undef ls
#undef rs
};
struct info_t{int val;info_t(int _val=0):val(_val){}};
struct tag_t{int tag;tag_t(int _tag=0):tag(_tag){}};
info_t operator +(info_t lhs,info_t rhs){return info_t(max(lhs.val,rhs.val));}
info_t operator +(info_t lhs,tag_t rhs){return info_t(max(lhs.val,rhs.tag));}
tag_t operator +(tag_t lhs,tag_t rhs){return tag_t(max(lhs.tag,rhs.tag));}
bool operator !=(tag_t lhs,tag_t rhs){return lhs.tag!=rhs.tag;}
Sgt<info_t,tag_t>sgt;
void dfs(int u,int pre){
mnv[u]=u;dfn[u]=++dfx;ord[dfx]=u;dep[u]=dep[pre]+1;
buc[dep[u]].emplace_back(dfn[u]);
q[u].emplace(u);
array<int,3>arr={u,inf,u};
for(auto v:g[u]){
if(v==pre)continue;
dfs(v,u);
while(dep[q[v].top()]-dep[u]>b)
q[v].pop();
mnv[u]=min(mnv[u],q[v].top());
if(q[v].top()<arr[0])swap(arr[0],arr[1]),arr[0]=q[v].top(),arr[2]=v;
else arr[1]=min(arr[1],q[v].top());
if(q[v].size()>q[u].size())
swap(q[u],q[v]);
while(!q[v].empty())
q[u].emplace(q[v].top()),q[v].pop();
}
rdfn[u]=dfx;
for(auto v:g[u]){
if(v==pre)continue;
omnv[v]=arr[arr[2]==v];
}
if(dep[u]+a-1<=n){
auto &vec=buc[dep[u]+a-1];
lbd[u]=lower_bound(vec.begin(),vec.end(),dfn[u])-vec.begin();
rbd[u]=upper_bound(vec.begin(),vec.end(),rdfn[u])-vec.begin();
}
}
void cdfs(int u,int pre,int mid){
nxt[u]=inf;
array<int,3>arr={inf,inf,-1};
for(auto v:g[u]){
if(v==pre)continue;
cdfs(v,u,mid);
nxt[u]=min(nxt[u],nxt[v]+1);
if(nxt[v]<arr[0])swap(arr[0],arr[1]),arr[0]=nxt[v],arr[2]=v;
else arr[1]=min(arr[1],nxt[v]);
}
array<int,2>son={0,0},key={0,0};
for(auto v:g[u]){
if(v==pre)continue;
if(lbd[v]<rbd[v]){
son[1]=son[0],son[0]=v;
for(int j=lbd[v];j<rbd[v];j++){
int pos=ord[buc[dep[v]+a-1][j]];
if(nxt[pos]>b&&dep[pos]>sgt.query(1,n,1,dfn[pos],dfn[pos]).val){
key[1]=key[0],key[0]=v;
break;
}
}
}
sgt.modify(1,n,1,dfn[v],rdfn[v],dep[u]+b-arr[arr[2]==v]-1);
}
for(auto v:g[u]){
if(v==pre)continue;
if(!son[son[0]==v]){
if(omnv[v]<=mid)
sgt.modify(1,n,1,dfn[v],rdfn[v],dep[u]+b);
}else if(!key[key[0]==v]){
sgt.modify(1,n,1,dfn[v],rdfn[v],dep[u]+b);
}
}
if(!son[0]){
if(mnv[u]<=mid)
nxt[u]=0;
}else if(!key[0]){
nxt[u]=0;
}
}
// template <typename T> T& chkmin(T& x, T y) {return x = min(x, y);}
// void cdfs(int x, int fa, int mid) {
// nxt[x] = inf;
// int mn1 = inf, id, mn2 = inf;
// for (int i: g[x])
// if (i != fa) {
// cdfs(i, x, mid), chkmin(nxt[x], nxt[i] + 1);
// if (nxt[i] < mn1) {
// mn2 = mn1;
// mn1 = nxt[i];
// id = i;
// } else chkmin(mn2, nxt[i]);
// }
// int id1 = 0, id2 = 0;
// int iid1 = 0, iid2 = 0;
// for (int i: g[x])
// if (i != fa) {
// if (lbd[i] < rbd[i]) {
// iid2 = iid1;
// iid1 = i;
// for(int j = lbd[i]; j < rbd[i]; j++) {
// int e = ord[buc[dep[x] + a][j]];
// if (nxt[e] > b && dep[e] > sgt.query(1, n, 1, dfn[e], dfn[e]).val) {
// id2 = id1, id1 = i;
// break;
// }
// }
// }
// sgt.modify(1, n, 1, dfn[i], rdfn[i], dep[x] + b - (id == i ? mn2 : mn1) - 1);
// }
// for (int i: g[x])
// if (i != fa) {
// bool flag;
// if (!(iid1 == i ? iid2 : iid1)) flag = omnv[i] <= mid;
// else flag = !(id1 == i ? id2 : id1);
// if (flag) sgt.modify(1, n, 1, dfn[i], rdfn[i], dep[x] + b);
// }
// bool flag;
// if (!iid1) flag = mnv[x] <= mid;
// else flag = !id1;
// if (flag) nxt[x] = 0;
// }
bool check(int mid){
sgt.clear();
cdfs(R,0,mid);
return !nxt[R];
}
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
cin>>n>>R>>a>>b;
if(a<=b)return cout<<1<<'\n',0;
for(int i=1,u,v;i<n;i++){
cin>>u>>v;
g[u].emplace_back(v),g[v].emplace_back(u);
}
dfs(R,0);
// for(int i=1;i<=n;i++){
// cout<<dfn[i]<<' '<<rdfn[i]<<' '<<mnv[i]<<' '<<omnv[i]<<' '<<lbd[i]<<' '<<rbd[i]<<'\n';
// }
// assert(false);
int l=1,r=n,res=0;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid))r=mid-1,res=mid;
else l=mid+1;
}
cout<<res<<'\n';
return 0;
}
详细
Subtask #1:
score: 1
Accepted
Test #1:
score: 1
Accepted
time: 0ms
memory: 38732kb
input:
300000 110732 1 1 54285 169439 18968 45543 130988 134682 162292 70081 212010 121474 128140 292466 209394 38279 91706 225569 67647 188578 265505 84279 161782 137098 27472 221980 284973 79104 230628 268631 69945 205947 153720 168119 230161 32244 138981 44376 165008 136947 125742 123375 209131 122038 8...
output:
1
result:
ok single line: '1'
Test #2:
score: 1
Accepted
time: 8ms
memory: 38724kb
input:
300000 123141 300000 300000 35459 173656 6934 241069 183095 87288 269195 16957 19492 242321 24470 81747 25697 172188 171424 220229 160473 69937 172168 99268 220664 39397 8212 2407 46718 94855 279515 295195 205222 167038 185958 111515 172553 45818 141322 214355 61335 64490 183502 105408 234540 245525...
output:
1
result:
ok single line: '1'
Test #3:
score: 1
Accepted
time: 4ms
memory: 38724kb
input:
298765 30225 2 3 265195 252069 113697 255482 227617 218688 279488 136408 179394 139291 86777 211320 255097 13136 68860 173342 178971 175020 278041 278319 285893 289677 194438 44163 56223 283058 110392 123602 20729 89517 152134 176747 121481 243463 297305 139297 244189 117068 181785 39468 154302 1860...
output:
1
result:
ok single line: '1'
Test #4:
score: 1
Accepted
time: 4ms
memory: 36676kb
input:
299987 224030 2 2 177674 20066 211112 287348 150440 136779 131528 209570 208840 36580 3395 152219 89118 44403 120439 274280 267578 80200 17796 257578 229408 211795 122773 147368 139779 842 94469 299092 211457 29057 9040 117449 216268 88141 40844 98163 183412 221031 230933 237086 147633 135982 282224...
output:
1
result:
ok single line: '1'
Test #5:
score: 1
Accepted
time: 0ms
memory: 36824kb
input:
2 1 1 2 2 1
output:
1
result:
ok single line: '1'
Subtask #2:
score: 4
Accepted
Test #6:
score: 4
Accepted
time: 2285ms
memory: 131480kb
input:
300000 226344 300 9 32176 183340 249597 14851 145160 92372 30564 242505 1140 169463 279867 14442 266653 32911 168819 26009 138049 133460 5327 103921 262703 112512 204338 84304 98144 9089 98632 238236 79093 101104 50327 237759 61236 275195 241153 116369 86842 272794 25675 121176 110170 225753 199931 ...
output:
1
result:
ok single line: '1'
Test #7:
score: 4
Accepted
time: 3102ms
memory: 131420kb
input:
299999 92073 2999 11 262905 260944 140896 162257 22797 193473 248112 247445 217760 68693 156294 167586 42291 233355 280566 247233 171395 239795 126564 179464 208554 185755 201665 156263 74786 85307 116366 163760 57326 143227 243541 149484 287792 283934 293052 265098 294245 296048 14582 36967 202999 ...
output:
245417
result:
ok single line: '245417'
Test #8:
score: 4
Accepted
time: 1671ms
memory: 131080kb
input:
298989 2 303 302 291949 291950 71254 71253 32103 32104 194290 194289 155694 155693 178665 178664 278674 278675 63793 63794 280321 280320 209075 209074 141282 141283 298423 298424 145067 145068 115803 115802 88974 88975 199766 199767 73340 73339 106776 106777 20786 20787 57085 57086 51034 51035 88299...
output:
3
result:
ok single line: '3'
Test #9:
score: 4
Accepted
time: 1702ms
memory: 131208kb
input:
298989 2 30001 30000 227255 227254 149938 149939 159449 159448 6194 6193 239990 239989 95657 95658 280931 280932 65015 65014 221854 221855 65661 65662 36912 36911 184778 184779 74520 74521 217578 217577 234314 234315 266126 266125 96469 96470 158616 158615 12920 12919 207237 207236 72167 72166 20226...
output:
3
result:
ok single line: '3'
Test #10:
score: 4
Accepted
time: 2970ms
memory: 128584kb
input:
289898 68514 42345 35 247935 196903 238347 177303 95489 261552 14797 183922 175677 109839 85928 186661 124668 74629 172100 214045 217602 46031 73083 257282 268102 276634 94408 248387 202292 208128 250155 61752 240022 256152 281659 223534 18580 272515 36 46287 247306 163047 90365 36426 241702 92561 6...
output:
289093
result:
ok single line: '289093'
Test #11:
score: 4
Accepted
time: 2063ms
memory: 130564kb
input:
298765 191954 298765 29876 158145 67683 17628 136757 153101 176403 952 52270 139224 227583 289601 4565 200272 19860 139873 277812 229381 251631 55892 22383 102701 27390 252623 286705 27875 223439 180032 271744 28933 296138 97573 294210 108654 126487 31902 223049 180647 68619 9869 147781 255029 23743...
output:
14
result:
ok single line: '14'
Test #12:
score: 4
Accepted
time: 2088ms
memory: 131004kb
input:
298765 33562 298764 29876 110929 69221 276688 201887 264415 65460 166102 272335 248892 186840 206217 296235 283621 86931 238780 122705 200845 137749 30491 75339 159784 24393 240809 7087 193364 245493 287660 2903 214506 285716 181040 49286 37334 6088 276968 3658 52998 220919 289624 131115 274518 6204...
output:
1
result:
ok single line: '1'
Test #13:
score: 4
Accepted
time: 2218ms
memory: 132204kb
input:
300000 1 150000 149999 139488 266956 75499 115106 197111 266846 75931 86565 243441 135464 194765 22597 286803 214206 236086 46031 227314 88097 71817 83460 61640 293618 211868 156133 1709 4302 274196 125332 204068 41865 21111 98062 21173 99704 125957 168343 251218 116725 230029 252274 195016 31148 11...
output:
2
result:
ok single line: '2'
Test #14:
score: 4
Accepted
time: 9ms
memory: 38800kb
input:
291234 289232 2 291234 56299 134830 146619 165289 230113 123453 264835 93343 140869 286284 36462 175435 204256 11688 180367 256764 193570 229161 64489 177626 22842 55205 118191 162946 194148 194973 96663 95195 157427 215291 227692 47027 219226 31692 198993 60149 39787 77693 127485 148991 216628 1999...
output:
1
result:
ok single line: '1'
Test #15:
score: 4
Accepted
time: 2314ms
memory: 131292kb
input:
300000 5 12 1 104098 71288 155929 237155 194885 110614 288708 131509 260955 5677 152237 222368 152814 51702 131846 277511 32293 143328 95240 144359 158319 206926 95983 78186 223795 104895 179277 77519 247023 263601 141002 229603 168689 271469 125125 273621 143596 40101 112050 30987 268143 178476 249...
output:
78
result:
ok single line: '78'
Test #16:
score: 4
Accepted
time: 2941ms
memory: 131372kb
input:
300000 18710 912 1 193195 34459 260311 292739 133324 164168 66161 138261 49021 172781 285599 274251 46667 124835 249174 273094 57936 232787 100855 137993 117133 208961 204288 165919 118007 11717 209150 1905 122223 56208 170266 110094 203532 80994 281756 254059 648 18645 264367 270340 276680 247873 2...
output:
246042
result:
ok single line: '246042'
Test #17:
score: 4
Accepted
time: 0ms
memory: 38676kb
input:
2 2 1 1 2 1
output:
1
result:
ok single line: '1'
Subtask #3:
score: 5
Accepted
Test #18:
score: 5
Accepted
time: 3ms
memory: 47036kb
input:
300 42 3 2 114 268 132 105 187 17 191 127 14 62 162 126 39 143 72 159 199 184 295 138 71 277 293 103 288 54 231 196 57 220 110 117 38 136 295 258 41 76 291 8 59 131 161 278 244 233 81 76 12 236 21 240 228 262 255 159 236 60 277 33 29 123 170 290 89 154 220 139 193 81 31 53 163 77 148 274 181 76 15 2...
output:
83
result:
ok single line: '83'
Test #19:
score: 5
Accepted
time: 3ms
memory: 44900kb
input:
300 178 3 2 277 106 123 105 235 290 273 34 300 180 43 55 239 74 19 138 110 201 295 18 207 97 238 177 114 24 195 219 154 186 151 294 143 291 47 293 33 99 2 46 101 39 109 240 15 256 43 121 205 261 267 257 81 167 82 23 300 182 13 46 195 221 163 17 109 93 144 23 110 17 153 129 91 243 281 74 135 72 145 1...
output:
4
result:
ok single line: '4'
Test #20:
score: 5
Accepted
time: 0ms
memory: 44988kb
input:
300 130 4 2 74 70 137 178 142 56 106 137 154 190 162 96 218 173 261 37 206 72 136 93 293 159 145 94 221 97 76 189 149 282 79 62 258 37 35 20 215 8 143 207 216 38 262 241 37 68 221 258 156 8 213 50 180 238 132 300 256 136 79 281 179 128 177 202 20 229 43 12 290 230 26 105 135 20 146 84 10 184 254 27 ...
output:
126
result:
ok single line: '126'
Test #21:
score: 5
Accepted
time: 0ms
memory: 44984kb
input:
300 49 4 2 199 123 264 232 60 265 215 2 226 189 160 11 200 217 194 175 295 203 20 165 203 63 132 127 42 259 170 293 230 269 20 166 141 96 149 210 246 122 5 185 90 156 297 21 300 78 24 94 139 154 268 258 53 15 267 67 221 248 298 154 136 254 192 234 142 170 56 217 90 25 228 216 216 186 61 90 14 221 27...
output:
26
result:
ok single line: '26'
Test #22:
score: 5
Accepted
time: 3ms
memory: 44968kb
input:
300 250 3 1 91 120 269 191 244 235 202 92 3 146 190 210 175 190 243 20 280 75 81 296 179 85 278 283 123 134 98 35 29 65 219 268 242 135 143 238 274 127 99 243 141 231 285 68 269 76 15 61 179 157 165 139 52 49 247 50 151 50 262 161 132 270 224 15 228 144 56 100 293 35 80 98 188 65 263 43 267 234 243 ...
output:
149
result:
ok single line: '149'
Test #23:
score: 5
Accepted
time: 0ms
memory: 42912kb
input:
300 205 3 1 43 211 182 106 31 159 33 141 50 122 33 108 65 275 218 285 263 71 39 211 41 91 264 151 211 286 298 228 84 96 292 176 78 239 107 28 247 265 132 182 225 257 70 58 165 61 162 35 221 23 168 234 279 130 111 261 157 34 61 47 299 97 129 233 247 245 280 60 137 252 241 248 275 91 251 178 288 181 2...
output:
45
result:
ok single line: '45'
Test #24:
score: 5
Accepted
time: 3ms
memory: 44984kb
input:
300 151 10 4 106 66 88 78 279 12 92 142 298 168 98 117 8 108 104 192 50 216 227 176 77 297 149 195 94 11 72 69 235 267 261 11 131 35 115 146 140 73 132 251 185 145 29 193 52 90 287 39 261 300 24 206 223 59 270 35 225 35 32 95 184 244 52 164 276 118 220 268 249 251 187 217 288 71 297 34 171 198 178 2...
output:
2
result:
ok single line: '2'
Test #25:
score: 5
Accepted
time: 5ms
memory: 46944kb
input:
300 203 300 10 2 182 179 26 120 101 281 271 236 75 260 242 121 271 32 66 277 14 98 47 152 83 231 39 145 93 23 127 203 76 76 252 65 31 33 62 60 201 154 147 42 83 13 203 203 2 265 292 96 30 23 85 23 64 220 30 189 277 296 44 63 110 107 202 61 93 134 286 65 122 133 241 152 142 97 84 209 202 267 47 255 8...
output:
1
result:
ok single line: '1'
Test #26:
score: 5
Accepted
time: 4ms
memory: 38796kb
input:
123 33 3 3 63 85 6 68 37 58 78 86 111 69 36 110 115 56 41 63 112 15 99 61 55 96 123 88 45 16 37 54 95 41 54 24 26 108 40 83 60 36 83 25 71 19 83 7 56 53 123 30 46 93 20 104 99 23 52 84 49 31 110 109 53 97 33 18 90 94 80 3 82 58 108 100 97 14 32 99 8 60 54 119 101 35 23 48 42 8 54 5 10 73 35 18 113 1...
output:
1
result:
ok single line: '1'
Test #27:
score: 5
Accepted
time: 6ms
memory: 46964kb
input:
231 165 100 50 114 20 131 183 182 20 31 36 210 93 13 188 175 5 154 63 48 24 205 90 146 153 129 186 156 106 27 82 49 198 89 42 111 146 203 142 87 20 98 188 65 63 196 118 15 102 137 75 101 67 143 160 130 197 186 209 50 172 47 224 4 220 59 41 148 16 32 182 131 90 87 225 177 77 149 30 93 33 51 106 185 1...
output:
1
result:
ok single line: '1'
Test #28:
score: 5
Accepted
time: 9ms
memory: 47128kb
input:
300 11 30 16 90 227 152 287 67 39 165 50 242 139 278 177 51 148 129 214 94 124 37 201 53 254 84 202 267 183 95 171 251 32 45 170 161 275 272 268 209 49 34 272 106 75 223 285 42 72 130 138 91 263 230 158 31 59 80 209 262 45 136 131 162 121 297 287 32 207 228 171 112 58 273 70 173 176 169 34 155 54 37...
output:
29
result:
ok single line: '29'
Subtask #4:
score: 3
Accepted
Dependency #3:
100%
Accepted
Test #29:
score: 3
Accepted
time: 9ms
memory: 47252kb
input:
3000 63 3 2 2155 250 1688 831 522 631 1755 1764 55 2251 2127 1756 1135 387 600 1437 182 1020 1802 1849 399 2974 1809 574 402 2032 2147 2561 1186 830 829 2804 1086 1237 82 414 892 375 107 2688 1857 1972 1162 324 1758 1763 1255 918 1553 908 849 1670 132 2126 2503 861 1906 1836 305 1063 922 6 2068 1435...
output:
878
result:
ok single line: '878'
Test #30:
score: 3
Accepted
time: 7ms
memory: 45200kb
input:
3000 528 3 2 2749 507 78 1098 1114 832 608 2375 2044 319 1549 1782 2146 1096 2728 817 1542 394 1362 2837 2714 2424 141 1693 190 2792 424 2422 2891 1525 1796 1932 2241 1427 790 1721 1044 1909 1240 2843 2964 1850 1587 2274 1249 1126 1 1689 2558 994 2911 2148 1160 1580 2530 2574 1402 1723 961 1518 2520...
output:
4
result:
ok single line: '4'
Test #31:
score: 3
Accepted
time: 9ms
memory: 45288kb
input:
3000 458 4 2 943 1128 2440 1236 1649 2508 2922 420 1540 1811 1710 566 1260 668 2124 858 78 373 551 1017 1611 1744 536 104 1999 2934 2391 354 765 675 301 316 301 1613 2919 2533 2604 301 443 1540 2287 1580 397 1970 1925 1439 2478 2414 2189 1169 521 2182 1700 163 2575 334 477 1728 581 332 45 2170 1485 ...
output:
1318
result:
ok single line: '1318'
Test #32:
score: 3
Accepted
time: 13ms
memory: 47240kb
input:
3000 2841 4 2 1502 2819 421 217 1423 1914 1968 2313 1207 544 2752 1319 2459 1345 2192 2421 1320 1368 2936 971 637 1964 1328 1901 1568 1868 1544 1357 308 2198 1883 2064 978 685 336 2521 2173 1402 1288 1166 1514 684 2369 771 1339 738 1446 2786 1060 1543 375 1947 1756 1912 1397 288 609 2230 1015 1187 2...
output:
174
result:
ok single line: '174'
Test #33:
score: 3
Accepted
time: 7ms
memory: 45212kb
input:
3000 2364 3 1 1809 381 674 1824 2549 125 1469 1465 1144 2486 1177 862 2559 1927 1211 36 630 739 2926 1555 1169 2479 2984 2956 1669 1009 398 2796 469 991 1886 2628 2770 2725 1216 1394 703 76 2016 1162 722 1840 78 2793 326 1057 918 1887 1291 2478 1160 1312 2990 801 2969 212 1727 2594 1727 1862 2541 62...
output:
2143
result:
ok single line: '2143'
Test #34:
score: 3
Accepted
time: 8ms
memory: 47228kb
input:
3000 2398 3 1 1889 2450 812 2135 1493 638 1854 1137 1252 648 166 265 1679 1601 1655 2909 1715 1976 1546 1236 2328 2749 983 332 515 133 1557 2018 2253 2065 756 358 2707 1881 706 944 2950 1419 359 2541 1612 628 2622 2164 2567 1293 1984 336 2502 2151 2056 780 59 374 1830 1407 102 1355 2783 1881 1798 15...
output:
149
result:
ok single line: '149'
Test #35:
score: 3
Accepted
time: 10ms
memory: 47208kb
input:
3000 1828 10 4 2915 1223 1673 262 2847 1682 2587 2184 1017 2101 847 948 882 1914 2341 737 1979 1325 1760 1181 2399 742 1265 589 2879 946 1350 1387 2257 460 2101 1349 1985 1386 2132 1234 2582 2928 1454 1911 2819 2291 2016 1584 2738 1284 1523 1881 2630 1557 2830 2492 2967 509 195 2535 2119 1901 1356 2...
output:
82
result:
ok single line: '82'
Test #36:
score: 3
Accepted
time: 10ms
memory: 47340kb
input:
3000 796 3000 10 1508 2938 1186 502 322 2126 1138 1034 1829 1180 897 2854 2944 1095 139 1107 934 599 2851 2720 2328 237 910 796 2326 2751 2034 1301 40 2974 1657 52 684 1644 1610 1646 273 2528 290 2608 2701 2094 1070 837 1574 834 1765 990 2457 1107 2239 449 129 2697 2871 1560 352 2310 1795 2670 673 9...
output:
1
result:
ok single line: '1'
Test #37:
score: 3
Accepted
time: 0ms
memory: 38808kb
input:
1234 899 3 3 232 1227 294 768 507 1064 255 524 116 946 1017 462 850 518 158 912 1190 127 451 1172 671 1119 279 853 706 634 144 243 1160 103 921 917 1078 748 320 1095 695 368 443 1089 186 39 548 540 1062 539 105 546 91 1188 333 462 930 1180 295 417 403 95 280 700 355 432 146 766 267 831 904 324 1047 ...
output:
1
result:
ok single line: '1'
Test #38:
score: 3
Accepted
time: 8ms
memory: 47212kb
input:
2345 36 100 50 1483 1104 731 1472 259 409 1410 1081 1914 802 45 1156 833 790 1092 900 1089 159 2235 2043 797 572 1616 1807 2027 1124 285 1920 607 1280 1034 114 1231 1540 777 1440 1507 2039 1603 3 681 1260 1053 2300 809 1913 1361 1763 1628 463 118 289 1395 2121 882 417 111 472 1279 1336 2324 136 2013...
output:
1
result:
ok single line: '1'
Test #39:
score: 3
Accepted
time: 14ms
memory: 47256kb
input:
3000 2763 10 5 2045 2874 920 2652 1567 2728 1201 2754 1503 1773 940 2797 440 1785 1936 2493 1789 1034 720 2004 1437 617 2787 256 427 757 224 2778 532 2547 2949 2504 1406 2895 1516 2218 2276 1366 742 2277 2636 2820 2465 1978 1742 696 553 697 930 421 1998 1400 188 684 423 2224 371 2083 471 3000 709 27...
output:
10
result:
ok single line: '10'
Test #40:
score: 3
Accepted
time: 10ms
memory: 43248kb
input:
3000 1809 100 50 970 2578 1613 803 2543 868 703 1731 1015 146 1894 806 2367 2708 704 2144 405 532 1795 1918 1337 1208 1084 1674 2609 2253 1847 1747 918 1461 1229 126 873 1948 2963 2499 1069 491 451 441 679 1752 2460 2688 149 557 1344 1848 2218 2066 31 895 1819 1349 37 750 2819 2216 504 2588 1571 226...
output:
1
result:
ok single line: '1'
Test #41:
score: 3
Accepted
time: 8ms
memory: 43240kb
input:
3000 428 1000 500 1235 2483 1038 1248 1686 1427 2539 417 1375 1120 1014 1266 647 2715 918 67 1920 1640 2892 543 2060 1215 816 292 2020 2318 2626 2711 1422 2207 605 2528 1035 1638 2716 2636 2101 2731 1720 2467 2239 1502 1418 2581 2039 2763 342 1047 2214 1403 2508 1845 330 2864 2069 1601 2439 1432 682...
output:
1
result:
ok single line: '1'
Test #42:
score: 3
Accepted
time: 11ms
memory: 45224kb
input:
3000 1830 10 5 707 2455 238 293 2333 1830 2357 142 2284 917 1948 951 626 1368 1644 2504 1736 552 2787 749 2072 626 1030 1830 2398 1863 1077 1265 1334 1117 681 1690 1552 890 2710 612 2675 1268 1755 1736 432 138 2902 1739 1692 1074 1443 1579 130 138 155 2440 469 2119 2537 784 1413 1830 1745 2420 1721 ...
output:
1
result:
ok single line: '1'
Test #43:
score: 3
Accepted
time: 10ms
memory: 43196kb
input:
3000 447 100 50 2018 1373 2585 1432 1765 2078 101 1994 2830 1867 2834 1388 2767 1133 2378 434 185 2560 1241 850 762 750 961 1204 1847 1893 481 304 2749 1149 994 447 2142 2480 1057 573 2080 1204 165 1133 285 1299 2403 985 447 438 2592 463 2561 729 2296 447 563 2749 205 382 2139 528 888 2378 1850 1861...
output:
1
result:
ok single line: '1'
Test #44:
score: 3
Accepted
time: 7ms
memory: 45220kb
input:
3000 2724 1000 500 2050 1598 989 1852 125 1601 2439 1517 497 2510 618 2747 486 1367 1942 527 400 136 1471 2724 2875 486 2471 2594 1328 667 824 2802 607 391 240 2849 2711 2439 1202 1944 1347 989 2375 2168 933 1827 1106 178 2194 734 2419 2811 601 528 2890 822 635 2395 832 2594 1383 2202 2088 1041 933 ...
output:
1
result:
ok single line: '1'
Test #45:
score: 3
Accepted
time: 10ms
memory: 45180kb
input:
3000 1779 3 2 2992 2251 1763 2992 691 2992 2992 2102 2344 57 1163 2559 2798 2992 534 394 719 1163 139 2992 1163 946 203 181 588 2992 2992 2825 1370 1349 2992 962 2992 2856 2584 863 1786 2992 2743 2992 434 2992 2992 1293 20 2992 2477 706 2992 251 2853 517 2612 2992 2992 1350 2992 310 2311 1163 2992 1...
output:
1
result:
ok single line: '1'
Test #46:
score: 3
Accepted
time: 10ms
memory: 43156kb
input:
2999 7 3 2 2618 877 314 2309 698 2889 717 877 877 2045 1747 111 698 2915 877 1558 698 1157 1369 877 1442 698 877 1466 698 883 877 87 1479 910 877 2221 2217 877 410 877 877 2048 1692 877 1868 877 537 1913 795 678 1013 877 2174 877 877 2385 608 698 877 1476 94 698 877 422 1297 698 1774 1002 698 2264 1...
output:
1
result:
ok single line: '1'
Test #47:
score: 3
Accepted
time: 8ms
memory: 45200kb
input:
2998 1036 3 2 2608 498 2961 1017 2608 2159 39 1501 1686 2608 2608 1494 428 2608 2681 1713 2608 2226 2608 1961 1800 2577 434 2681 186 1561 2608 2666 1772 2608 2197 2416 2608 1651 1797 457 2903 2608 2385 2608 2400 1937 2608 2051 1424 372 2608 1034 2791 2608 2608 27 2608 659 900 2608 2028 1866 2681 397...
output:
2
result:
ok single line: '2'
Test #48:
score: 3
Accepted
time: 12ms
memory: 45824kb
input:
3000 40 300 160 52 244 261 122 1943 809 993 895 2718 1514 1252 1384 1376 2663 2050 2398 704 335 1045 1867 2846 2330 851 1543 2756 875 99 105 1765 2714 2218 1170 2586 2581 2340 2594 897 447 2235 2369 1648 1017 1353 1209 2553 2198 595 929 1928 2104 1523 1173 2526 2565 1696 474 2523 1581 1053 1968 1932...
output:
281
result:
ok single line: '281'
Subtask #5:
score: 4
Accepted
Test #49:
score: 4
Accepted
time: 625ms
memory: 55224kb
input:
100000 20749 3 2 89778 51257 2293 75317 20142 42260 55350 69024 2419 90402 2248 71914 60607 94307 33933 57799 79884 93934 9788 53542 18109 28742 7700 93763 12102 78825 34580 61577 84344 12887 63610 12371 30988 75638 47533 66209 95296 22495 12638 545 36347 57495 41813 49592 60342 1881 38899 62345 524...
output:
43056
result:
ok single line: '43056'
Test #50:
score: 4
Accepted
time: 525ms
memory: 53368kb
input:
100000 81436 3 2 30487 98338 75456 42340 35081 95919 14744 79324 12767 72910 10330 15285 18425 40190 49306 55115 27041 60644 82901 10649 43365 29415 57822 86861 83007 50520 39798 89642 44146 63575 29824 89809 23549 45972 89791 83570 13656 1315 63396 74190 21244 80244 90922 97110 38966 92339 84884 89...
output:
717
result:
ok single line: '717'
Test #51:
score: 4
Accepted
time: 623ms
memory: 55060kb
input:
100000 8852 4 2 40452 57256 17799 88040 60724 53958 13290 90136 19267 49330 97135 48815 91159 71145 11677 334 6176 11175 2311 36476 80261 78319 22343 42921 53692 9431 20138 8540 15962 57516 66603 41779 22916 82799 36377 26000 46797 3889 5764 3600 76457 13146 41675 46067 65577 93967 3461 31914 46191 ...
output:
66085
result:
ok single line: '66085'
Test #52:
score: 4
Accepted
time: 614ms
memory: 54928kb
input:
100000 16035 4 2 43071 56048 63171 4393 98259 47823 2561 96442 9238 88690 85973 58025 9308 88080 16242 96064 88566 55956 57022 90692 84895 82151 27964 28817 24774 35654 35624 93885 37408 43501 89095 11303 1737 8666 378 67623 56302 11639 22263 32297 12188 72428 49974 80854 29579 370 70340 55421 4511 ...
output:
13134
result:
ok single line: '13134'
Test #53:
score: 4
Accepted
time: 640ms
memory: 52836kb
input:
100000 85235 3 1 94738 24340 59327 27917 90855 27869 97393 55723 50462 24028 27405 59525 40629 84195 41269 21311 97793 12448 94822 90533 96359 70118 59964 12798 51098 68286 58527 7816 41817 19034 10924 54535 63191 97115 60743 79349 6864 76498 29085 92310 8063 41260 11214 91868 23225 2976 50822 99018...
output:
86829
result:
ok single line: '86829'
Test #54:
score: 4
Accepted
time: 566ms
memory: 52564kb
input:
100000 96572 3 1 36159 41653 67667 34037 37976 63963 45201 5393 52221 59416 54961 13650 28764 99209 60804 67606 48624 79765 41041 83510 51667 65582 53730 45676 22269 64403 52565 21021 64941 4761 62855 69936 67203 18060 91572 33888 52593 86981 38287 22045 72710 6674 19970 36871 12501 91926 14428 9425...
output:
12008
result:
ok single line: '12008'
Test #55:
score: 4
Accepted
time: 520ms
memory: 54104kb
input:
100000 73324 10 4 71933 28912 87834 88149 44971 99521 60861 82846 97055 92782 56244 87280 53155 84157 70530 70324 79371 71634 21639 40110 75095 53060 6988 96059 21201 57449 65138 12755 88230 54355 87152 56089 86570 76587 79256 65685 16310 13946 41916 10874 9161 88963 90203 58683 76300 29464 25230 30...
output:
513
result:
ok single line: '513'
Test #56:
score: 4
Accepted
time: 393ms
memory: 54128kb
input:
100000 15636 100000 10 10243 50231 32391 7992 18149 2934 33787 51982 96445 22322 41361 80285 17777 24611 69149 49364 87021 54306 89564 43531 90973 83603 85869 90213 27390 88410 38427 49151 77811 41575 32541 86212 92924 21286 47549 65738 76763 15623 17786 10339 32880 76070 9809 67114 91819 43885 7140...
output:
1
result:
ok single line: '1'
Test #57:
score: 4
Accepted
time: 536ms
memory: 54520kb
input:
100000 42996 20 10 74902 50663 7097 23701 45735 7288 52375 46377 46724 63127 89073 24467 29104 28729 83469 85669 70860 88962 78797 72790 27570 86063 24686 20963 90850 57413 17431 29758 84798 67397 74951 85193 37009 12044 56862 33692 23929 61577 18914 38454 58446 32853 69649 68901 55638 59986 47751 1...
output:
221
result:
ok single line: '221'
Test #58:
score: 4
Accepted
time: 585ms
memory: 54132kb
input:
100000 98739 100 10 85414 42813 17848 77599 42506 71989 1918 745 9097 91249 79539 71491 71938 77961 66338 99594 19970 52870 38371 91469 69665 44311 13354 45803 56738 89880 46844 51870 38831 48646 37471 66852 2177 16313 35195 71674 8625 70549 1856 78239 9309 43203 4214 95780 29103 47895 69129 78296 4...
output:
14017
result:
ok single line: '14017'
Test #59:
score: 4
Accepted
time: 526ms
memory: 54032kb
input:
100000 29573 10000 10 54397 69025 83525 16322 69843 91831 18296 65353 43293 19327 70856 30469 80150 62236 40232 32171 68933 90628 66837 2965 54776 47328 62998 65584 23455 70312 34594 26099 90702 38631 99042 75615 83802 53660 60219 72548 22411 34554 71451 67910 31284 17953 55582 86186 80488 79094 180...
output:
4314
result:
ok single line: '4314'
Test #60:
score: 4
Accepted
time: 400ms
memory: 55416kb
input:
100000 80902 11 10 90717 1067 6057 7613 33217 91418 62156 49414 35712 58370 3406 3782 14422 36383 13121 54659 75065 82970 75833 76063 45137 74130 15269 84206 55939 35132 58683 99724 10608 64362 97967 78859 87661 3406 18955 76762 80678 25453 18179 44046 76792 92120 94865 94823 41467 53099 16426 15081...
output:
1
result:
ok single line: '1'
Test #61:
score: 4
Accepted
time: 4ms
memory: 38684kb
input:
100000 10278 10 10 22080 78739 83644 60650 84023 10536 67793 39227 64817 3246 95349 11887 32894 95918 57769 72231 70181 74963 19829 86171 64925 17589 77353 21140 73018 75509 80759 72751 77187 23048 67991 3801 84230 36205 67544 76682 47475 7799 55601 5047 33506 35435 84123 96632 55627 68456 12697 632...
output:
1
result:
ok single line: '1'
Test #62:
score: 4
Accepted
time: 2ms
memory: 38688kb
input:
56789 52146 3 3 5472 30471 5612 23037 21888 4725 9673 14647 40053 18588 21170 12453 8765 7882 10193 30274 4849 41647 31241 54244 14257 31966 15987 54036 16735 44259 53171 6717 55365 38027 42958 27812 48238 1399 3252 46229 5390 16924 29962 31185 34680 46655 43807 6253 1971 15286 53171 8341 8324 41346...
output:
1
result:
ok single line: '1'
Test #63:
score: 4
Accepted
time: 429ms
memory: 52948kb
input:
87654 33545 100 10 76907 51162 2915 42413 34214 66794 26541 46255 64067 84944 39351 71693 45020 7870 24345 49823 43523 68748 18308 78976 46430 4311 73739 13607 4941 68811 33354 64770 22269 605 65058 33589 73005 12430 4881 65990 15196 24871 74977 64963 26162 16647 25414 25820 62913 18924 45927 6426 5...
output:
312
result:
ok single line: '312'
Test #64:
score: 4
Accepted
time: 547ms
memory: 51760kb
input:
100000 15972 3 2 4042 27219 48452 50004 24050 15265 98768 92464 84229 32638 37774 25749 60779 4042 22693 4042 20459 60049 31647 92464 85570 4042 32048 66569 15807 66317 4042 40632 58038 4042 4042 42309 91476 92464 56479 4042 4042 99680 44063 92464 91388 4042 4042 20396 90085 4042 92464 42365 52267 4...
output:
1
result:
ok single line: '1'
Test #65:
score: 4
Accepted
time: 548ms
memory: 54256kb
input:
99999 81648 3 2 9887 25839 25256 91573 49540 29303 57225 9887 9887 70368 71428 9887 75119 43654 49540 10823 9887 46802 67383 9887 39690 78526 15448 9887 9887 74383 2408 35602 27412 26263 9887 5426 68446 21949 22730 9887 40208 9887 85864 9887 9887 29904 9887 43673 27973 9887 9887 76950 9887 18302 535...
output:
1
result:
ok single line: '1'
Test #66:
score: 4
Accepted
time: 562ms
memory: 54028kb
input:
99998 21401 3 2 86802 83093 22689 98078 98078 27135 86802 27190 86802 24635 86802 48361 86802 15404 91042 86802 55168 80091 58962 86802 86802 63714 92439 12924 86802 91316 42935 86802 86802 77106 25977 86802 86802 36711 81148 17527 13300 86802 29366 86802 70356 66339 55207 86802 51397 86802 86802 33...
output:
2
result:
ok single line: '2'
Test #67:
score: 4
Accepted
time: 1097ms
memory: 75160kb
input:
100000 19380 10000 10 29035 13872 72983 17203 73146 17085 96627 62817 82836 37282 7304 48599 99013 20988 19677 50106 6143 51794 67680 23396 66608 38204 64941 92480 9700 67672 76815 73041 48776 50729 93872 94057 95160 30168 71242 31768 15672 49775 4195 55846 92771 77623 11578 31199 44029 7070 9075 90...
output:
99529
result:
ok single line: '99529'
Subtask #6:
score: 6
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Test #68:
score: 6
Accepted
time: 672ms
memory: 53940kb
input:
100000 79681 3 2 65943 25943 64751 74801 57286 6984 13774 36580 23143 82174 51469 96068 24596 77451 94363 13896 18470 19474 68028 3059 77 13602 54700 3984 8188 60238 6007 78575 95532 21455 13378 39417 45536 60395 98017 33987 84394 70544 93145 46410 48606 72175 73854 64081 49684 71878 99672 4760 6897...
output:
54486
result:
ok single line: '54486'
Test #69:
score: 6
Accepted
time: 575ms
memory: 52220kb
input:
100000 15840 3 2 88368 32222 72516 57332 71137 45652 77873 56262 17321 97378 24618 90143 49976 42914 68448 43878 26069 61922 66409 18799 2863 2605 26978 13318 61711 22341 32818 34273 50934 1012 78542 98376 31868 61940 4802 84964 23060 90806 12184 16593 48704 99283 91878 58705 63067 58968 66058 42911...
output:
877
result:
ok single line: '877'
Test #70:
score: 6
Accepted
time: 671ms
memory: 53872kb
input:
100000 73721 4 2 46271 35241 36492 95324 35040 65653 3396 11262 86051 42210 7656 47964 45764 93238 80057 74793 20067 84113 55042 51695 70839 11606 47168 88124 99709 62149 61079 56998 1321 35438 72354 52617 76073 68697 73197 45844 8059 17400 50545 3861 60037 17731 27907 90079 93031 41726 4140 68737 4...
output:
48942
result:
ok single line: '48942'
Test #71:
score: 6
Accepted
time: 545ms
memory: 54676kb
input:
100000 15578 4 2 10111 53492 9632 67579 38724 95534 49283 80843 19512 41050 39897 18101 79808 87308 66915 22116 78652 36288 60878 44610 85811 34036 91901 93037 36311 74017 31790 10603 24695 61447 86163 32832 30865 43354 11672 29472 67030 54060 62821 74540 45414 69779 52870 32616 91156 45581 46750 85...
output:
7354
result:
ok single line: '7354'
Test #72:
score: 6
Accepted
time: 646ms
memory: 54408kb
input:
100000 6124 3 1 40762 76226 78347 57394 42752 9861 45489 22823 97528 13512 62525 17178 14194 85285 81172 58828 45011 4468 13452 59004 41399 15658 87883 49748 30178 94468 38448 50063 54553 31024 82794 18937 93680 89151 9925 52234 64352 21350 3317 11169 77606 94917 141 68896 55015 84146 85623 72438 16...
output:
86867
result:
ok single line: '86867'
Test #73:
score: 6
Accepted
time: 522ms
memory: 52904kb
input:
100000 66738 3 1 89639 69778 97184 25998 88179 69822 33957 26151 64809 22942 53225 83132 62441 90673 45849 68376 91087 15230 64047 25497 47739 61833 30108 24118 66142 14266 96942 43993 56876 60628 46767 66099 26036 18948 6706 14340 21439 63182 13202 5528 18019 74383 63793 98431 87351 86472 72529 747...
output:
30
result:
ok single line: '30'
Test #74:
score: 6
Accepted
time: 525ms
memory: 53816kb
input:
100000 96793 10 4 34642 34513 32968 61036 33772 17291 85054 7799 82168 14086 7392 19287 9364 92784 79175 25948 19843 8845 49235 23348 6666 97397 20732 5709 77156 38850 59993 90802 89186 34888 62803 58581 93237 34131 68467 55638 97575 87364 97572 57676 28223 2964 93324 79533 57578 44083 53803 8191 84...
output:
902
result:
ok single line: '902'
Test #75:
score: 6
Accepted
time: 405ms
memory: 52532kb
input:
100000 31181 100000 10 63022 92673 71462 25888 96677 29578 40335 3175 37598 54692 87495 95461 74095 66117 87555 59227 23600 62523 61412 89310 11847 26874 16359 50211 64895 16886 97596 53308 94245 45884 2139 67854 68955 32836 58723 55149 46463 77115 26337 59216 77087 4813 93502 63267 34202 59007 2482...
output:
1
result:
ok single line: '1'
Test #76:
score: 6
Accepted
time: 0ms
memory: 38684kb
input:
56789 39098 3 3 3481 5161 8435 13125 14466 50352 50533 50600 47604 33073 24477 8464 51147 44938 9183 52936 31467 16896 55568 3221 25223 34105 7469 20422 10345 38508 19441 44228 50779 46533 11647 28715 56050 19508 24770 13778 17071 35596 53790 1570 6184 30111 32063 18940 51267 46295 56724 33863 45912...
output:
1
result:
ok single line: '1'
Test #77:
score: 6
Accepted
time: 504ms
memory: 52920kb
input:
87654 56358 100 50 72317 47978 78856 36640 56770 18011 61973 67563 39185 24373 26244 45718 53264 41636 7511 7878 20021 84381 18394 54550 76972 86488 9599 57482 7435 75084 16143 50154 14905 40301 80886 11064 66613 84558 82371 6010 54230 3706 31448 65385 47640 15115 70498 26741 12831 48221 56635 38218...
output:
21
result:
ok single line: '21'
Test #78:
score: 6
Accepted
time: 545ms
memory: 54084kb
input:
100000 3380 3 2 95383 48360 7742 14053 48360 64436 48360 68606 86415 14053 14053 66772 13208 48360 63092 48360 66713 48360 84475 48360 48360 9230 43859 48360 75049 48360 48360 86137 6625 14053 70128 48360 14053 64172 86581 48360 48360 5797 48360 87148 48360 66607 62350 14053 45081 69852 48360 62061 ...
output:
3
result:
ok single line: '3'
Test #79:
score: 6
Accepted
time: 563ms
memory: 52920kb
input:
99999 283 3 2 18003 77557 18003 73195 18003 11504 84779 18003 60285 18003 12091 18003 18003 63586 18003 87953 75864 54787 18003 15884 88267 18003 65215 68596 1668 18003 19890 1733 18003 73447 41965 19890 83746 19890 19890 62816 74315 41461 18003 33472 97612 18003 19890 79178 30835 18003 18003 88576 ...
output:
2
result:
ok single line: '2'
Test #80:
score: 6
Accepted
time: 526ms
memory: 53044kb
input:
99998 86848 3 2 30752 74647 74647 28077 88760 93457 8086 64715 47530 70402 46833 74647 64362 70402 958 70402 69672 74647 95576 74647 16639 74647 74647 3331 61704 85738 70402 64904 74647 6261 32964 71233 17337 74647 92328 74647 59157 74647 70402 96228 57055 67097 74647 35812 74647 30326 74647 36722 7...
output:
4
result:
ok single line: '4'
Test #81:
score: 6
Accepted
time: 428ms
memory: 60708kb
input:
100000 1 33333 33328 94382 66665 43697 43699 43843 43844 1775 1776 66665 90038 12053 12054 13919 13921 15801 15802 27739 27740 1737 1735 66665 80744 50031 50032 61407 61409 12298 12297 50393 50394 43195 43197 61597 61598 76614 66665 72865 66665 13863 13864 71983 66665 74061 66665 35661 35663 3685 36...
output:
11
result:
ok single line: '11'
Test #82:
score: 6
Accepted
time: 699ms
memory: 73924kb
input:
100000 2 49997 49996 30182 32936 77595 21981 20003 45252 40044 67777 53886 34134 1385 53439 85622 80855 76058 73770 61477 46723 31775 33113 76864 67259 34565 75668 99797 35534 86877 44523 93890 66595 82568 69278 36734 23229 66325 90336 63054 44201 40689 8074 98229 28489 38172 12835 55741 74112 13232...
output:
3
result:
ok single line: '3'
Test #83:
score: 6
Accepted
time: 543ms
memory: 55044kb
input:
100000 23650 10 5 6859 14146 23398 9444 13470 12125 14605 49681 94926 36754 44629 38656 69557 49347 80719 13804 35100 77977 81231 81049 20843 1399 32621 50817 57927 4514 17141 47658 59273 1469 35638 12421 85111 67386 70981 90375 22037 18096 29074 50820 17370 51159 85602 73431 31092 94880 3608 36076 ...
output:
33
result:
ok single line: '33'
Test #84:
score: 6
Accepted
time: 463ms
memory: 55520kb
input:
100000 7634 1000 500 26044 18744 20860 11629 30315 82992 66874 77260 90681 77225 7716 64640 79644 51041 56528 32972 45743 36456 68388 47032 32036 73640 24008 7603 64360 89766 30115 60265 36728 98245 84409 9646 99108 91167 82750 96204 61774 88997 53081 49206 95785 65194 27079 83951 10170 25471 93531 ...
output:
4
result:
ok single line: '4'
Test #85:
score: 6
Accepted
time: 464ms
memory: 54236kb
input:
100000 50421 10000 5000 42449 770 50346 12283 66063 47493 90198 42136 92907 57042 81469 22353 51160 4455 48973 77857 55044 58108 46191 96928 87025 41563 93925 22658 71490 71127 83482 59187 79881 83962 77717 71456 31681 50447 98014 64711 49166 14558 96049 60117 94924 1718 57224 89983 24710 54449 4590...
output:
1
result:
ok single line: '1'
Test #86:
score: 6
Accepted
time: 373ms
memory: 53380kb
input:
100000 28604 10 5 76715 37086 82111 70907 38220 49776 81068 85777 10761 25003 24093 92795 17142 37290 74598 5574 75843 70852 75456 62758 18128 73283 3436 89461 77282 13159 41088 1729 69015 88993 55182 44879 8000 73441 27521 38465 62850 68916 32073 76871 44311 30880 32015 56897 67265 9504 13885 88290...
output:
1
result:
ok single line: '1'
Test #87:
score: 6
Accepted
time: 390ms
memory: 53512kb
input:
100000 70083 1000 500 79817 74215 98708 70083 49220 42573 8890 98801 6676 14305 33040 61966 28387 2752 53585 220 24896 89007 57711 72529 76140 14929 40341 40434 49748 64622 6536 45952 78825 81216 42300 25903 88124 14721 27015 57021 327 93146 20736 24202 11404 18409 9217 72420 95437 20947 21350 51505...
output:
1
result:
ok single line: '1'
Test #88:
score: 6
Accepted
time: 374ms
memory: 54760kb
input:
100000 49562 10000 5000 46498 10815 15301 81790 53499 96895 25387 93111 22587 68868 49916 40273 97590 28896 23455 23544 27726 18526 16305 83834 79034 62591 73816 49801 53963 31994 64514 37320 40421 78013 5956 20002 53211 70013 51300 76968 80718 8602 54413 85265 88046 90969 6153 69178 6073 85535 8226...
output:
1
result:
ok single line: '1'
Test #89:
score: 6
Accepted
time: 588ms
memory: 74368kb
input:
100000 46154 50000 49999 47016 38897 66925 18825 48698 77234 30283 12445 86129 46153 45150 25969 79369 31992 75455 8768 47253 47772 10254 32169 60935 67226 92351 62295 93937 1162 25602 11603 58899 13959 69361 69866 54500 95204 23487 36100 82384 8308 43341 78933 44496 2751 30240 23478 68152 33192 132...
output:
1
result:
ok single line: '1'
Test #90:
score: 6
Accepted
time: 487ms
memory: 73716kb
input:
100000 1 50000 49999 62814 81308 83268 72606 90333 10041 59862 24350 522 42186 7635 22675 84956 21271 32197 2726 19300 95110 67592 4855 63062 43807 38925 33677 14431 28147 763 32650 64829 26232 21616 4751 7883 98794 11936 49487 44782 89199 49831 71583 59058 42561 5103 2354 47803 28007 64252 36786 88...
output:
2
result:
ok single line: '2'
Test #91:
score: 6
Accepted
time: 482ms
memory: 54960kb
input:
100000 1 35 16 61195 30615 11466 22898 79689 39862 8743 4389 9984 5009 83343 41689 19770 39505 16986 8510 88240 44137 28192 56350 12176 24318 66328 33181 47343 94651 33090 16562 6714 3374 5449 2742 2267 4500 39411 19723 18100 9067 22159 44283 5258 10482 34539 69043 29935 59835 46988 23511 48206 9637...
output:
20
result:
ok single line: '20'
Test #92:
score: 6
Accepted
time: 536ms
memory: 55000kb
input:
100000 86267 25 13 31258 30976 55837 34236 13603 66227 17602 74672 45672 36434 75574 77180 69881 3266 11502 55644 35400 14755 2033 86491 91832 32566 73769 65604 93477 71194 1543 92861 19242 89206 12774 16599 46244 99939 15099 87663 72373 12062 44723 15389 51573 51867 80435 41110 30656 84423 9645 140...
output:
1
result:
ok single line: '1'
Subtask #7:
score: 2
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Dependency #6:
100%
Accepted
Test #93:
score: 2
Accepted
time: 2498ms
memory: 72192kb
input:
300000 290458 3 2 89761 242981 239856 72617 49395 258412 214882 238523 3741 219396 149053 261989 143898 100394 236293 214322 183884 127661 253450 172599 127103 222607 121038 286388 253783 260105 262460 11641 223888 141812 139608 211436 52679 225192 121955 200346 66338 244580 281902 252206 202908 121...
output:
126815
result:
ok single line: '126815'
Test #94:
score: 2
Accepted
time: 2117ms
memory: 70408kb
input:
300000 86076 3 2 192090 92834 200602 23391 275886 155394 175446 187906 189963 139779 82798 235190 273267 282337 222837 107550 182767 287331 170630 202465 176885 99079 113728 12960 155256 115856 285506 263655 28762 212259 178240 101131 270358 111895 220430 235930 103834 124132 283107 23817 65663 2068...
output:
4855
result:
ok single line: '4855'
Test #95:
score: 2
Accepted
time: 2515ms
memory: 72344kb
input:
300000 170191 4 2 16574 147311 288893 73391 43950 140133 74896 207857 271478 267503 194299 128859 299909 54527 100286 242939 85436 183966 125702 53056 115594 161896 170191 222795 110979 73759 299352 123549 156411 212807 188697 146351 231330 257460 82761 67078 230489 123981 247793 246240 264858 66564...
output:
211431
result:
ok single line: '211431'
Test #96:
score: 2
Accepted
time: 1986ms
memory: 70332kb
input:
300000 67839 4 2 122158 220335 181421 41073 80274 176431 24875 7209 48672 9983 2146 83291 23974 240091 32270 245573 157650 8719 295275 141835 194195 64245 161688 251783 236149 147863 150823 100887 43776 105861 135220 49060 95987 269789 258161 27722 247979 276974 195838 88170 117013 181619 221335 206...
output:
3206
result:
ok single line: '3206'
Test #97:
score: 2
Accepted
time: 2638ms
memory: 68652kb
input:
300000 253332 3 1 234880 197301 205934 281725 111844 62266 218532 74288 260502 173488 221078 6258 182874 76732 225788 36888 91168 88859 109931 222053 259698 113858 170110 282913 187448 20575 296641 76912 26580 210930 133813 60018 169211 279314 298320 286804 183289 67738 110675 267060 271764 296175 1...
output:
277508
result:
ok single line: '277508'
Test #98:
score: 2
Accepted
time: 2319ms
memory: 68148kb
input:
300000 251657 3 1 4992 249899 196161 133998 87909 268432 87422 194568 168919 135619 252547 132113 194530 125463 250006 252692 43479 97786 261448 18200 155902 171878 190185 293686 214697 295642 30402 24431 10153 238214 131296 140542 127891 177424 177138 12341 50445 189862 98605 143563 229389 273076 1...
output:
61573
result:
ok single line: '61573'
Test #99:
score: 2
Accepted
time: 2217ms
memory: 72972kb
input:
300000 293301 10 4 102251 187866 296151 13576 236821 246660 183203 193550 221660 99413 113982 121315 211748 86782 270705 205531 202933 270912 41554 140278 121800 214485 286689 117927 253194 76580 261878 47329 88906 40729 82853 76309 109640 116207 228876 234613 181642 19781 234536 127666 271615 10870...
output:
12815
result:
ok single line: '12815'
Test #100:
score: 2
Accepted
time: 1569ms
memory: 72648kb
input:
300000 155627 300000 10 40858 150635 126587 136137 236524 156676 43350 148390 5297 193787 55897 3503 30015 99455 78725 49413 162963 257357 206359 247685 41894 78801 257900 218692 8262 243269 94649 202127 48607 74232 107474 45731 28923 161101 29189 57940 162692 65960 173051 165824 206709 171516 19041...
output:
1
result:
ok single line: '1'
Test #101:
score: 2
Accepted
time: 4ms
memory: 38788kb
input:
123456 97061 3 3 36201 20383 72504 17901 113906 110459 45160 119290 88126 56049 51576 106238 76991 106556 13724 51300 72397 79347 121708 60994 51197 102699 103764 2993 19149 75835 105123 116056 5671 49130 111421 5719 4327 104838 96789 55536 20866 100325 81615 108178 26363 29011 41151 72783 11898 108...
output:
1
result:
ok single line: '1'
Test #102:
score: 2
Accepted
time: 1674ms
memory: 67060kb
input:
234567 41757 100 50 163988 175287 4714 34399 167778 55032 121173 182879 86304 65616 132400 175558 185865 113945 212313 204991 10861 146094 104443 83009 96696 230946 14524 30230 149764 67520 133628 232100 176691 209619 97994 1896 120782 13574 124669 103304 33302 138431 211232 69531 123862 104422 2202...
output:
167
result:
ok single line: '167'
Test #103:
score: 2
Accepted
time: 2291ms
memory: 68992kb
input:
300000 42115 3 2 158430 54017 125298 158430 158430 52707 134630 158430 295323 158430 158430 218355 244742 107425 135194 251000 158430 35359 135194 20534 167594 135194 180229 135194 175132 210310 261554 158430 215134 158430 135194 161995 252523 158430 22550 158430 194447 158430 251627 135194 189429 1...
output:
3
result:
ok single line: '3'
Test #104:
score: 2
Accepted
time: 2223ms
memory: 68556kb
input:
299999 123015 3 2 43267 274745 7856 274745 199438 67591 28239 164187 274745 190891 156106 69573 274745 31165 274745 282561 274745 130029 219980 274745 88356 274745 274745 119066 69573 167954 12336 102991 15025 274745 263487 274745 255001 274745 274745 35038 274745 60968 259392 274745 274745 38760 15...
output:
3
result:
ok single line: '3'
Test #105:
score: 2
Accepted
time: 2334ms
memory: 68456kb
input:
299998 147099 3 2 135683 191977 15452 135683 135683 258805 5362 135683 135683 65145 135683 90649 135683 150419 195201 135683 58287 135683 93365 135683 125237 205676 135683 27337 135683 83990 135683 282255 135683 276620 114589 135683 203668 135683 135683 12349 8972 135683 19343 252642 160348 135683 1...
output:
1
result:
ok single line: '1'
Test #106:
score: 2
Accepted
time: 1738ms
memory: 89108kb
input:
300000 1 100000 99995 228565 199999 164245 164246 20687 20688 165127 165129 30061 30062 199999 233044 199999 237685 117203 117205 182380 182379 227768 199999 153046 153045 51481 51483 57857 57858 38700 38699 199999 253412 273619 199999 186127 186125 42137 42135 261945 199999 2363 2365 65055 65057 19...
output:
11
result:
ok single line: '11'
Test #107:
score: 2
Accepted
time: 3051ms
memory: 132200kb
input:
300000 2 149997 149996 103876 154476 290403 103399 121986 102822 224408 75127 218876 152753 149690 241597 162318 285564 220962 55945 199129 144008 38064 105046 163598 21703 185682 134544 162514 256468 78340 240242 171359 23964 181690 201790 247680 229546 52285 83680 297092 229030 164908 61752 58460 ...
output:
3
result:
ok single line: '3'
Test #108:
score: 2
Accepted
time: 2025ms
memory: 71976kb
input:
300000 153275 10 5 57007 270358 292455 58806 113253 53959 82971 149250 111658 194090 23743 90634 239745 238756 190461 76153 142527 139298 21540 64839 264560 97331 215734 249630 280487 28684 145425 51850 69951 97411 56350 72946 5150 218152 225137 80140 3779 8274 250534 260817 159548 125312 120085 260...
output:
377
result:
ok single line: '377'
Test #109:
score: 2
Accepted
time: 1769ms
memory: 74740kb
input:
300000 56122 1000 500 246373 20136 104868 177579 100842 150848 15078 235482 19856 184750 134314 8915 58979 222496 212411 268221 36949 84430 148081 30710 126133 160752 97886 115389 119983 23729 51289 3725 183583 171240 197491 114140 246857 84944 9813 14295 66599 287014 116416 2606 77767 128126 221865...
output:
39
result:
ok single line: '39'
Test #110:
score: 2
Accepted
time: 1802ms
memory: 74204kb
input:
300000 98831 10000 5000 4239 35126 99874 192127 265897 50401 69434 229928 95860 49388 168392 267856 189823 175233 82158 151132 194071 127447 156599 103159 196171 58144 34403 283834 291414 96086 35473 248369 233530 221294 191449 198016 90215 155610 123062 137560 85938 80477 11163 88070 80492 218879 2...
output:
1
result:
ok single line: '1'
Test #111:
score: 2
Accepted
time: 1472ms
memory: 71864kb
input:
300000 212269 10 5 46564 268709 32227 2609 101942 34886 104834 18648 240730 186632 143277 187160 174786 75074 243711 243429 97064 156744 230737 293552 186857 170262 34886 176348 189923 127221 145930 135537 273328 254691 80534 18036 141741 113307 101175 189154 198049 33816 84822 97166 160678 204198 1...
output:
1
result:
ok single line: '1'
Test #112:
score: 2
Accepted
time: 1468ms
memory: 71732kb
input:
300000 251749 1000 500 35439 61509 189598 41088 176523 232044 124688 86626 43566 103515 120785 45632 127042 200459 43124 261083 160724 208283 26546 156263 118925 280264 67757 285991 120910 299264 221863 225018 96511 198980 120538 199052 149704 249354 267371 85710 278505 219190 299918 62321 180716 15...
output:
1
result:
ok single line: '1'
Test #113:
score: 2
Accepted
time: 1493ms
memory: 71828kb
input:
300000 172 10000 5000 55932 68691 87348 227644 228603 53019 84441 174413 80117 45127 167355 155721 66182 28788 259714 165825 32678 49925 211070 94693 240041 146882 8172 296581 90926 151556 260560 81718 136291 31760 5017 37681 31476 47785 153621 222893 41121 204659 79187 244542 19044 292291 85789 872...
output:
1
result:
ok single line: '1'
Test #114:
score: 2
Accepted
time: 2858ms
memory: 129560kb
input:
300000 149359 150000 149999 129991 293025 46422 119528 229449 139502 123467 39703 122920 21527 74087 11061 19505 280399 99852 282861 276885 202410 164338 75723 275167 228020 297453 26274 206564 95117 108348 178597 27564 233240 148000 129627 183726 231811 245199 194668 221999 134597 235830 173092 105...
output:
1
result:
ok single line: '1'
Test #115:
score: 2
Accepted
time: 2294ms
memory: 132228kb
input:
300000 1 150000 149999 164998 106271 26192 297974 24769 243344 114798 106556 170625 134814 203289 196660 187507 30083 72441 18245 275800 170178 7556 23647 127682 295756 126792 171169 296870 93092 45815 61096 168145 60968 165268 120227 242565 186568 298589 166203 199915 159804 234696 181293 78621 281...
output:
2
result:
ok single line: '2'
Test #116:
score: 2
Accepted
time: 1845ms
memory: 76940kb
input:
300000 1 40 20 53283 106526 98238 196437 155871 77955 135507 67773 39226 78412 140415 280790 145324 290609 95763 191487 33415 16727 7268 14496 11768 23497 6261 12482 229160 114600 125423 250806 114263 228487 39121 19580 16597 8318 56196 112352 81775 40907 129268 258497 48047 24043 16525 33010 118836...
output:
21
result:
ok single line: '21'
Test #117:
score: 2
Accepted
time: 1939ms
memory: 77096kb
input:
300000 47555 20 10 85793 201771 49365 14072 175087 163257 293254 71137 96418 30434 215168 177212 76848 290622 8163 296487 281972 252186 296151 170649 214588 170735 35406 104857 32795 201951 26479 299251 124069 141132 287994 65733 192747 19487 42244 291234 63598 240315 254716 23884 247129 109235 4767...
output:
1
result:
ok single line: '1'
Extra Test:
score: 0
Extra Test Passed