Submission #620064

#	Time	Username	Problem	Language	Result	Execution time	Memory
620064		AlperenT	Minerals (JOI19_minerals)	C++17	40 / 100	26 ms	8652 KiB

minerals

#include <bits/stdc++.h>
#include "minerals.h"

using namespace std;

const int N = 43000 + 5;

int n, ans[N], ptr, cnt;

vector<int> a, b;

int query(int x){
    return cnt = Query(x);
}

struct SegTree{
    vector<int> tree[N * 4];

    void build(int v = 1, int l = 1, int r = n){
        if(l == r) ans[l] = tree[v].front();
        else{
            int m = l + (r - l) / 2;

            while(ptr < m){
                ptr++;
                query(a[ptr - 1]);
            }

            while(ptr > m){
                query(a[ptr - 1]);
                ptr--;
            }

            for(auto x : tree[v]){
                int prvcnt = cnt;

                query(x);

                if(cnt == prvcnt + 1) tree[v * 2 + 1].push_back(x);
                else tree[v * 2].push_back(x);

                query(x);
            }

            build(v * 2 + 1, m + 1, r);
            build(v * 2, l, m);
        }
    }
};

SegTree sgt;

void Solve(int N_) {
    n = N_;

    for(int i = 1; i <= n * 2; i++){
        int prvcnt = cnt;

        query(i);

        if(cnt == prvcnt + 1) a.push_back(i);
        else{
            query(i);
            b.push_back(i);
        }
    }

    for(auto x : a) query(x);

    for(auto x : b) sgt.tree[1].push_back(x);

    sgt.build();

    for(int i = 1; i <= n; i++) Answer(a[i - 1], ans[i]);
}

• 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