xor 쿼리 (벡터버젼)

스타벅스 쿠폰을 위한 위대한 도전이 시작된다.

11.1     시간초과가 뜬다.

// Example program

#include <iostream>

#include <string>

#include <vector>

using namespace std;

int quick_selection(int a, int n, vector<int> ArrList, int k);

int main()

{

    vector<int> v;

    v.reserve(500000);

    vector<int>::iterator iter;

    

    int queryNum;

    int totalNum;

    int x,L,R;

    cin >> totalNum;

    for (int i=0; i<totalNum; i++) {

        cin >> queryNum;

        if (queryNum == 1) {

            cin >> x;

            v.push_back(x);            

        }

        else if (queryNum == 2) {

            cin >> L >> R >> x;

            int biggestXor = 0;

            int y = 0;

            for (iter = v.begin()+L-1; iter!=v.begin()+R; iter++) {

                int didXor = *iter ^ x;

                if (didXor >= biggestXor) {

                    biggestXor = didXor;

                    y = *iter;

                }

            }

            

            cout << y << endl;

        }

        

        else if (queryNum == 3) {

            int deleteNum;

            cin >> deleteNum;

            v.erase(v.end()-deleteNum,v.end());

        }

        

        else if (queryNum == 4) {

            cin >> L >> R >> x;

            int smallNums = 0;

            for (iter = v.begin()+L-1; iter!=v.begin()+R; ++iter) {

                if (*iter <= x) smallNums++;

            }

            cout << smallNums << endl;

        }

        

        else if (queryNum == 5) {

            cin >> L >> R >> x;

            cout << quick_selection(L,R,v,x) << endl;

            

        }

    }

        

    return 0;

}

int quick_selection(int a, int n, vector<int> ArrList, int k)

{

    int start = a-1;

    int end = n-1;

 

    while (start < end)

    {

        int i = start;

        int j = end;

        int mid = ArrList[(i + j)/2];

 

        while (i < j)

        {

            if(ArrList[i] >= mid)

            {

                int tmp = ArrList[j];

                ArrList[j] = ArrList[i];

                ArrList[i] = tmp;

                j--;

            } else {

                i++;

            }

        }

 

        if (ArrList[i] > mid)

            i--;

 

        if (k <= i)

            end = i;

        else

            start = i + 1;

    }

    

    if (start == end) return ArrList[n-1];

    return ArrList[k-1];

}