Submission #623350

#	Time	Username	Problem	Language	Result	Execution time	Memory
623350		AlperenT	Minerals (JOI19_minerals)	C++17	100 / 100	471 ms	17024 KiB

minerals

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

using namespace std;

const int N = 50000 + 5;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

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

vector<int> a, b;

set<int> cur;

int query(int x){
    if(cur.find(x) != cur.end()) cur.erase(x);
    else cur.insert(x);

    return cnt = Query(x);
}

struct SegTree{
    map<int, vector<int>> tree;

    void build(int v = 1, int l = 1, int r = n, bool flag = false){
        if(l > r) return;

        if(l == r) ans[l] = tree[v].front();
        else{
            int m = l + (r - l) * 0.373;

            for(int i = l; i <= m; i++) query(a[i - 1]);

            for(auto x : tree[v]){
                if(tree[v * 2].size() == (m - l + 1)) tree[v * 2 + 1].push_back(x);
                else if(tree[v * 2 + 1].size() == (r - (m + 1) + 1)) tree[v * 2].push_back(x);
                else{
                    if(cur.find(x) == cur.end()){
                        int prevcnt = cnt;

                        query(x);

                        if(prevcnt + 1 == cnt) tree[v * 2 + flag].push_back(x);
                        else tree[v * 2 + !flag].push_back(x);
                    }
                    else{
                        int prevcnt = cnt;

                        query(x);

                        if(prevcnt == cnt) tree[v * 2 + !flag].push_back(x);
                        else tree[v * 2 + flag].push_back(x);
                    }
                }
            }

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

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 b.push_back(i);
    }

    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]);
}

Compilation message (stderr)

minerals.cpp: In member function 'void SegTree::build(int, int, int, bool)':
minerals.cpp:36:39: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |                 if(tree[v * 2].size() == (m - l + 1)) tree[v * 2 + 1].push_back(x);
      |                    ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
minerals.cpp:37:48: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |                 else if(tree[v * 2 + 1].size() == (r - (m + 1) + 1)) tree[v * 2].push_back(x);
      |                         ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~

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