QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#469129 | #6400. Game: Celeste | 233L | TL | 0ms | 18476kb | C++14 | 3.2kb | 2024-07-09 14:43:28 | 2024-07-09 14:43:28 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define uint unsigned int
#define ldb long double
#define pii pair<int,int>
#define mkp make_pair
#define mkt make_tuple
#define fr first
#define se second
#define uset unordered_set
#define umap unordered_map
#define pqueue priority_queue
#define all(_box) _box.begin(),_box.end()
#define ppc __builtin_popcount
#define ctz __builtin_ctz
#define clz __builtin_clz
#define lbd lower_bound
#define ubd upper_bound
#define deb(x) cerr<<#x<<'='<<(x)<<' '
using namespace std;
const int base=1000999;
const int N=1e6+4;
ull pw[N];
int n;
int a[N],b[N];
vector<int>ans;
int rot[N];
namespace SMT{
int cnt;
struct node{
int ls,rs,l,r;
ull hash_val;
}st[30*N];
#define ls(id) st[id].ls
#define rs(id) st[id].rs
void push_up(int id){
st[id].hash_val=st[ls(id)].hash_val*pw[st[rs(id)].r-st[rs(id)].l+1]+st[rs(id)].hash_val;
}
void build(int &id,int l,int r){
assert(cnt+1<30*N);
id=++cnt,st[id].l=l,st[id].r=r;
if(l==r)return;
int mid=(l+r)>>1;
build(ls(id),l,mid);
build(rs(id),mid+1,r);
}
void update(int &id,int pos){
if(st[id].l>pos||st[id].r<pos)return;
assert(cnt+1<30*N);
st[++cnt]=st[id],id=cnt;
if(st[id].l==st[id].r){
st[id].hash_val++;
return;
}
update(ls(id),pos);
update(rs(id),pos);
push_up(id);
}
bool comp_(int p,int q){//check if p>q
if(st[p].l==st[p].r)
return st[p].hash_val>st[q].hash_val;
if(st[rs(p)].hash_val!=st[rs(q)].hash_val)
return comp_(rs(p),rs(q));
return comp_(ls(p),ls(q));
}
bool comp(int p,int q){
if(st[p].hash_val==st[q].hash_val)return 0;
return comp_(p,q);
}
void print(int id){
if(st[id].l==st[id].r){
for(int i=0;i<int(st[id].hash_val);i++)
ans.push_back(st[id].l);
return;
}
print(rs(id));
print(ls(id));
}
#undef ls
#undef rs
}
using SMT::update;
using SMT::comp;
void solve(){
int l,r;
cin>>n>>l>>r;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
SMT::build(rot[1],1,n);
update(rot[1],b[1]);
deque<int>q;
for(int i=2,p=1;i<=n;i++){
while(a[i]-a[p]>=l){
if(rot[p]){
while(!q.empty()&&comp(rot[p],rot[q.back()]))q.pop_back();
q.push_back(p);
}
p++;
}
while(!q.empty()&&a[i]-a[q.front()]>r)q.pop_front();
if(q.empty())rot[i]=0;
else update(rot[i]=rot[q.front()],b[i]);
}
if(!rot[n])cout<<-1<<'\n';
else{
ans.clear();
SMT::print(rot[n]);
cout<<ans.size()<<'\n';
for(int i:ans)cout<<i<<' ';
cout<<'\n';
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
pw[0]=1;
for(int i=1;i<N;i++)
pw[i]=pw[i-1]*base;
int T;
cin>>T;
while(T--){
SMT::cnt=0;
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 18476kb
input:
2 5 2 3 1 2 3 4 5 5 2 3 1 4 3 1 2 1 4 7 3 3 3
output:
3 5 4 3 -1
result:
ok 3 lines
Test #2:
score: -100
Time Limit Exceeded
input:
10000 57 8 11 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 11 16 7 7 10 13 9 14 10 1 12 4 8 13 3 20 16 7 16 19 20 8 19 7 16 6 17 13 7 19 17 11 12 17 6 3 7 8 14 2 4 15 5 18 16 7 20 9 1...