QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#751322 | #9574. Strips | Crying# | WA | 22ms | 7832kb | C++14 | 3.1kb | 2024-11-15 18:08:19 | 2024-11-15 18:08:20 |
Judging History
answer
#include<bits/stdc++.h>
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define mid ((l+r)>>1)
using namespace std;
typedef long long ll;
typedef array<int,2> pr;
const int N = 2e5+10,INF = 2e9;
template<typename T>void tomin(T& x,T y){x = min(x,y);}
template<typename T>void tomax(T& x,T y){x = max(x,y);}
//
int T,n,m,k,w;
pr a[N]; int tot,ans,res;
int dp[N],b[N],cur,pre[N];
const pr Z = {INF,INF};
struct Seg{
pr t[N<<2];
void pu(int x){t[x] = min(t[lc(x)],t[rc(x)]);}
void build(int x,int l,int r){
t[x] = Z;
if(l==r)return;
build(lc(x),l,mid); build(rc(x),mid+1,r);
}
void mdf(int x,int l,int r,int p,pr v){
if(l==r)return tomin(t[x],v);
(p<=mid) ? mdf(lc(x),l,mid,p,v) : mdf(rc(x),mid+1,r,p,v);
pu(x);
}
pr qry(int x,int l,int r,int ql,int qr){
if(ql>qr)return Z; if(ql<=l && qr>=r)return t[x];
pr res = Z;
if(ql<=mid)tomin(res,qry(lc(x),l,mid,ql,qr));
if(qr>mid)tomin(res,qry(rc(x),mid+1,r,ql,qr));
return res;
}
}seg;
int qry(int x){return lower_bound(b+1,b+1+cur,x)-b;}
int rqry(int x){return upper_bound(b+1,b+1+cur,x)-b-1;}
vector<int> rev;
void cov(int L,int R){
int x = L;
while(x<=R){
rev.push_back(x);
x += k;
}
}
void solve(){
cin>>n>>m>>k>>w; ans = 0; rev.clear();
tot = 0; a[++tot] = {0,0}; a[++tot] = {w+1,0};
for(int i=1,x;i<=n;i++)cin>>x,a[++tot] = {x,1};
for(int i=1,x;i<=m;i++)cin>>x,a[++tot] = {x,0};
sort(a+1,a+1+tot);
//
for(int l=1,r;l<tot;l=r){
r = l+1; while(r<=tot && a[r][1])r++;
if(l==r-1)continue;
//
cur = 0;
for(int i=l+1;i<r;i++)b[++cur] = a[i][0]%k; sort(b+1,b+1+cur); cur = unique(b+1,b+1+cur)-b-1;
seg.build(1,1,cur);
dp[l] = 0;
for(int i=l+1;i<r;i++){
if(dp[i-1] != INF){
seg.mdf(1,1,cur,qry(a[i][0]%k),(pr){dp[i-1]-a[i][0]/k,i});
}
dp[i] = INF; int dis = a[i+1][0] - a[i][0]; pr tmp = Z;
//(a[i][0],k)的部分
pr val = seg.qry(1,1,cur,qry(a[i][0]%k+1),rqry(min(k-1,a[i][0]%k+dis)));
if(val[0] != INF){
val[0] += a[i][0] / k;
tomin(tmp,val);
}
//[0,a[i][0]]的部分
dis -= k - a[i][0]%k;
val = seg.qry(1,1,cur,1,rqry(min(a[i][0]%k,dis)));
if(val[0] != INF){
val[0] += a[i][0] / k + 1;
tomin(tmp,val);
}
//
if(tmp[0] != INF){
dp[i] = tmp[0];
pre[i] = tmp[1];
}
}
if(dp[r-1] == INF){
cout<<"-1\n";
return;
}
ans += dp[r-1];
for(int j=r-1;j>l;j=pre[j]-1){
cov(a[pre[j]][0],a[j][0]);
}
}
cout<<ans<<"\n";
sort(rev.begin(),rev.end()); for(auto u : rev)cout<<u<<" "; cout<<"\n";
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>T;
while(T--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7784kb
input:
4 5 2 3 16 7 11 2 9 14 13 5 3 2 4 11 6 10 2 1 11 2 1 2 6 1 5 3 2 1 2 6 1 5 2
output:
4 2 7 10 14 -1 2 1 5 -1
result:
ok ok 4 cases (4 test cases)
Test #2:
score: -100
Wrong Answer
time: 22ms
memory: 7832kb
input:
11000 3 8 2 53 32 3 33 35 19 38 20 1 30 10 6 7 10 1 42 3 14 4 36 28 40 22 17 20 12 41 27 7 1 19 13 9 6 6 13 78 55 76 53 32 54 58 62 45 21 4 7 61 8 7 3 68 9 26 54 31 22 3 38 65 34 16 58 47 52 29 53 5 8 4 33 33 5 30 6 15 27 12 9 28 19 2 13 10 6 1 2 48 8 12 48 1 41 31 40 7 6 7 61 20 19 30 52 49 17 40 3...
output:
2 3 32 7 3 4 14 22 28 36 40 -1 8 3 9 22 25 31 38 54 65 3 5 15 30 8 1 8 12 31 41 43 45 47 4 17 30 37 49 2 52 67 1 27 1 22 -1 -1 2 4 31 -1 -1 3 25 30 42 3 3 17 60 -1 2 54 66 3 50 59 65 3 50 60 78 -1 -1 -1 -1 -1 -1 -1 3 25 27 44 3 7 8 36 -1 -1 -1 1 38 -1 4 35 43 87 91 4 18 28 43 47 ...
result:
wrong answer Participant didn't find a solution but the jury found one. (test case 3)