QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#128348#6400. Game: CelesteEnergy_is_not_overML 0ms0kbC++175.0kb2023-07-20 21:37:272023-07-20 21:37:28

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-20 21:37:28]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2023-07-20 21:37:27]
  • 提交

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 ...

result: