Submission #1225239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225239		MarwenElarbi	Minerals (JOI19_minerals)	C++20	25 / 100	43 ms	7392 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;

//CODE

vector<int> tab[43000*4];
vector<pair<int,int>> ans;
set<int> st;
set<int> st_;
int lst;
void daq(int pos,int l,int r){
    if(l>r) return;
    if(l==r){
        if(st_.count(l)) lst=Query(l);
        ans.push_back({l,tab[pos].back()});
        return;
    }
    int mid=(r+l)/2;
    int i=r;
    while(i>mid){
        lst=Query(i);
        st_.erase(i);
        i--;
    }
    if(st.count(tab[pos][0])){
        for(auto u:tab[pos]){
            int a=Query(u);
            st.erase(u);
            if (a<lst) tab[pos*2+2].push_back(u);
            else tab[pos*2+1].push_back(u);
            lst=a;
        }
        daq(pos*2+1,l,mid);
        while(i<=r){
            lst=Query(i);
            st_.insert(i);
            i++;
        }
        daq(pos*2+2,mid+1,r);
    }else{
        for(auto u:tab[pos]){
            int a=Query(u);
            st.insert(u);
            //cout <<"hey"<<" "<<u<<" "<< a <<" "<<lst<<endl;
            if (a>lst) tab[pos*2+2].push_back(u);
            else tab[pos*2+1].push_back(u);
            lst=a;
        }
        daq(pos*2+1,l,mid);
        while(i<=r){
            lst=Query(i);
            st_.insert(i);
            i++;
        }
        daq(pos*2+2,mid+1,r);
    }
    return;
}

void Solve(int N) {
    lst=0;
    for (int i = N+1; i <= 2*N; ++i)
    {
        tab[0].push_back(i);
        lst=Query(i-N);
    }
    daq(0,1,N);
    for (int i = 0; i < ans.size(); ++i)
    {
        Answer(ans[i].first,ans[i].second);
    }
}

• Subtask 1: 0 / 6
• Subtask 2: 25 / 25
• Subtask 3: 0 / 9
• Subtask 4: 0 / 30
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10