Submission #1225249

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225249		MarwenElarbi	Minerals (JOI19_minerals)	C++20	40 / 100	109 ms	12736 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_;
vector<int> lleft;
vector<int> rright;
int lst;
void daq(int pos,int l,int r){
    /*cout <<pos<<" "<<l<<" "<<r<<endl;
    for (int i = 0; i < tab[pos].size(); ++i)
    {
        cout << tab[pos][i]<<" ";
    }cout <<endl;*/
    if(l>r) return;
    if(l==r){
        //if(st_.count(l)) lst=Query(l);
        ans.push_back({lleft[l],tab[pos].back()});
        return;
    }
    int mid=(r+l)/2;
    int i=r;
    while(i>mid){
        lst=Query(lleft[i]);
        st_.erase(lleft[i]);
        i--;
    }
    if(st.count(tab[pos][0])){
        for(auto u:tab[pos]){
            int a=Query(u);
            //cout << "hey"<< " "<<" "<<u<<" "<<l<<" "<<r<<endl;
            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(lleft[i]);
            st_.insert(lleft[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(lleft[i]);
            st_.insert(lleft[i]);
            i++;
        }
        daq(pos*2+2,mid+1,r);
    }
    return;
}

void Solve(int N) {
    lleft.push_back(0);
    rright.push_back(0);
    lst=0;
    for (int i = 1; i <= 2*N; ++i)
    {
        int a=Query(i);
        if(a>lst) lleft.push_back(i);
        else rright.push_back(i);
        lst=a;
    }
    for (int i = 1; i <= N; ++i)
    {
        tab[0].push_back(rright[i]);
        st.insert(rright[i]);
    }
    daq(0,1,N);
    for (int i = 0; i < ans.size(); ++i)
    {
        Answer(ans[i].first,ans[i].second);
    }
}

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 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