QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#128348 | #6400. Game: Celeste | Energy_is_not_over | ML | 0ms | 0kb | C++17 | 5.0kb | 2023-07-20 21:37:27 | 2023-07-20 21:37:28 |
Judging History
answer
//
// Created by Barichek on 20.07.2023 14:00:52
//
#include <bits/stdc++.h>
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define all(a) a.begin(), a.end()
#define len(a) (int) (a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
#ifdef Energy_is_not_over
#define DEBUG for (bool ____DEBUG = true; ____DEBUG; ____DEBUG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (false)
#define LOG(...)
#endif
const int max_n = 1e6+10, inf = 1000111222;
int x[max_n];
int a[max_n];
int l[max_n];
int r[max_n];
vector<int> vh[max_n];
int dp[max_n];
typedef pii hash_type;
struct vertex
{
int l,r;
hash_type h;
};
vertex V[max_n*40];
int last_v=0;
int build_empty_tree(int l,int r)
{
int res=last_v++;
if (l==r){
return res;
}
int m=(l+r)/2;
V[res].l=build_empty_tree(l,m);
V[res].r=build_empty_tree(m+1,r);
return res;
}
const int md1=1e9+7;
const int md2=1e9+9;
const int base=12412527;
hash_type combine_hashes(const hash_type& lhs, const hash_type& rhs)
{
pii res;
res.fir=(1ll*(lhs.fir+10)*base+(rhs.fir+100))%md1;
res.sec=(1ll*(lhs.fir+10)*base+(rhs.fir+100))%md2;
return res;
}
int apply(int v,int l,int r,int pos)
{
int res=last_v++;
V[res]=V[v];
if (l==r){
V[res].h.fir++;
V[res].h.sec++;
return res;
}
int m=(l+r)/2;
if (pos<=m){
V[res].l=apply(V[v].l,l,m,pos);
}
else{
V[res].r=apply(V[v].r,m+1,r,pos);
}
V[res].h=combine_hashes(V[V[res].l].h,V[V[res].r].h);
return res;
}
bool better(int v1,int v2,int l,int r)
{
if (l==r){
LOG("compare better",l,V[v1].h.fir,V[v2].h.fir);
return V[v1].h.fir>V[v2].h.fir;
}
int m=(l+r)/2;
if (V[V[v1].r].h != V[V[v2].r].h){
return better(V[v1].r,V[v2].r,m+1,r);
}
else{
return better(V[v1].l,V[v2].l,l,m);
}
}
void get_result(int v,int l,int r,vector<int>& res)
{
if (l==r){
for (int i=0;i<V[v].h.fir;i++){
res.pb(l);
}
return;
}
int m=(l+r)/2;
get_result(V[v].r,m+1,r,res);
get_result(V[v].l,l,m,res);
}
void solve()
{
int n,L,R;
cin>>n>>L>>R;
for (int i=0;i<n;i++){
cin>>x[i];
}
for (int i=0;i<n;i++){
cin>>a[i];
}
/// l[i] r[i]
{
int cur_l=0;
int cur_r=-1;
for (int i=0;i<n;i++){
while (x[i]-x[cur_l]>R){
cur_l++;
}
while (cur_r+1<i && x[i]-x[cur_r+1]>=L){
cur_r++;
}
l[i]=cur_l;
r[i]=cur_r;
LOG(i,l[i],r[i]);
}
}
for (int i=0;i<n;i++){
vh[i].clear();
}
for (int i=1;i<n;i++){
if (l[i]<=r[i]){
vh[r[i]].pb(i);
dp[i]=+inf;
}
else{
dp[i]=-inf;
}
}
deque<int> q;
dp[0]=apply(build_empty_tree(1,n),1,n,a[0]);
q.pb(0);
int last_added_r=0;
for (int i=1;i<n;i++){
while (!q.empty() && q[0]<l[i]){
q.pop_front();
}
while (last_added_r+1<=r[i]){
last_added_r++;
while (dp[last_added_r]!=-inf && !q.empty() && better(dp[last_added_r],dp[q.back()],1,n)){
q.pop_back();
}
if (dp[last_added_r]!=-inf){
q.push_back(last_added_r);
}
}
DEBUG{
LOG("when taking",i);
cerr<<"q :: ";
for (auto i:q){
cerr<<i<<" ";
}
cerr<<"\n";
};
int buf=(dp[i]==-inf || q.empty() || q[0]>r[i] ? -inf : dp[q[0]]);
if (buf!=-inf){
buf=apply(buf,1,n,a[i]);
}
dp[i]=buf;
/// 16:20
DEBUG{
LOG(i);
if (dp[i]==-inf){
LOG("-inf");
}
else{
vector<int> res;
get_result(dp[i],1,n,res);
cerr<<"res :: ";
for (auto i:res){
cerr<<i<<" ";
}
cerr<<"\n";
}
};
}
if (dp[n-1]==-inf){
cout<<-1<<"\n";
}
else{
vector<int> res;
get_result(dp[n-1],1,n,res);
cout<<len(res)<<"\n";
for (auto i:res){
cout<<i<<" ";
}
cout<<"\n";
}
}
int main() {
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
int tests;
cin>>tests;
while (tests--){
solve();
}
return 0;
}
詳細信息
Test #1:
score: 0
Memory Limit Exceeded
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:
21984 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...