Submission #65104

#	Time	Username	Problem	Language	Result	Execution time	Memory
65104		bazsi700	Cake (CEOI14_cake)	C++14	50 / 100	2068 ms	8764 KiB

cake

#include <bits/stdc++.h>

using namespace std;

struct Block {
    bool L;
    int prevblocksizesl;
    int prevblocksizesr;
    int siz;
    vector<pair<int,int> > tops;
};

int arr[250005];
int ans[250005];

//14:45-19:45

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,A;
    cin >> n >> A;
    vector<pair<int,int> > tosort (n);
    vector<int> smallranks;
    for(int i = 1; i <= n; i++) {
        cin >> arr[i];
        tosort[i-1] = {arr[i],i};
    }
    sort(tosort.begin(),tosort.end());
    for(int i = n-1; i >= max(n-11,0); i--) {
        smallranks.push_back(tosort[i].second);
    }
    int Q;
    cin >> Q;
    vector<pair<int,int> > quer(Q);
    int fcn = 0;
    int ecn = 0;
    for(int i = 0; i < Q; i++) {
        char ch;
        cin >> ch;
        if(ch == 'F') {
            int pos;
            cin >> pos;
            quer[i] = {pos,-1};
            fcn++;
        } else {
            int pos,ran;
            cin >> pos >> ran;
            quer[i] = {pos,ran};
            ecn++;
        }
    }
    if((n <= 10000 && Q <= 10000) || fcn <= 500) {
        for(auto q : quer) {
            if(q.second == -1) {
                int pos = q.first;
                if(pos == A) {
                    cout << "0\n";
                    continue;
                }
                int leftind = A-1;
                int rightind = A+1;
                for(int i = 1; i < n; i++) {
                    if(leftind == 0) {
                        if(rightind == pos) {
                            cout << i << "\n";
                            break;
                        }
                        rightind++;
                        continue;
                    }
                    if(rightind == n+1) {
                        if(leftind == pos) {
                            cout << i << "\n";
                            break;
                        }
                        leftind--;
                        continue;
                    }
                    if(arr[leftind] < arr[rightind]) {
                        if(leftind == pos) {
                            cout << i << "\n";
                            break;
                        }
                        leftind--;
                        continue;
                    } else {
                        if(rightind == pos) {
                            cout << i << "\n";
                            break;
                        }
                        rightind++;
                        continue;
                    }
                }
            } else {
                int pos = q.first;
                int ran = q.second;
                bool cont = false;
                for(int el : smallranks) {
                    if(el == pos) {
                        cont = true;
                    }
                }
                if(!cont) {
                    vector<int> nwv;
                    for(int i = 0; i < ran-1; i++) {
                        nwv.push_back(smallranks[i]);
                    }
                    nwv.push_back(pos);
                    for(int i = ran-1; i <= min(n-1,10); i++) {
                        nwv.push_back(smallranks[i]);
                    }
                    swap(nwv,smallranks);
                } else {
                    vector<int> nwv;
                    for(int i = 0; i < ran-1; i++) {
                        nwv.push_back(smallranks[i]);
                    }
                    nwv.push_back(pos);
                    for(int i = ran-1; i <= min(n-1,10); i++) {
                        if(smallranks[i] != pos) {
                            nwv.push_back(smallranks[i]);
                        }
                    }
                    swap(nwv,smallranks);
                }
                int prv = -1;
                for(int i = 0; i <= 10; i++) {
                    int el = smallranks[i];
                    if(el == pos) {
                        if(i != smallranks.size()-1) {
                            arr[el] = arr[smallranks[i+1]]+1;
                        } else {
                            arr[el] = arr[smallranks[i-1]]-1;
                        }
                        break;
                    }
                    arr[el]++;
                }
                /*for(int i = 1; i <= n; i++) {
                    cout << arr[i] << " ";
                }
                cout << endl;*/
            }
        }
    } else {

        int leftind = A-1;
        int rightind = A+1;
        for(int i = 1; i < n; i++) {
            if(leftind == 0) {
                ans[rightind] = i;
                rightind++;
                continue;
            }
            if(rightind == n+1) {
                ans[leftind] = i;
                leftind--;
                continue;
            }
            if(arr[leftind] < arr[rightind]) {
                ans[leftind] = i;
                leftind--;
                continue;
            } else {
                ans[rightind] = i;
                rightind++;
                continue;
            }
        }
        for(auto q : quer) {
            if(q.second == -1) {
                int pos = q.first;
                cout << ans[pos] << "\n";

            } else {
                int pos = q.first;
                int ran = q.second;
                bool cont = false;
                for(int el : smallranks) {
                    if(el == pos) {
                        cont = true;
                    }
                }
                if(!cont) {
                    vector<int> nwv;
                    for(int i = 0; i < ran-1; i++) {
                        nwv.push_back(smallranks[i]);
                    }
                    nwv.push_back(pos);
                    for(int i = ran-1; i <= min(n-1,10); i++) {
                        nwv.push_back(smallranks[i]);
                    }
                    swap(nwv,smallranks);
                } else {
                    vector<int> nwv;
                    for(int i = 0; i < ran-1; i++) {
                        nwv.push_back(smallranks[i]);
                    }
                    nwv.push_back(pos);
                    for(int i = ran-1; i <= min(n-1,10); i++) {
                        if(smallranks[i] != pos) {
                            nwv.push_back(smallranks[i]);
                        }
                    }
                    swap(nwv,smallranks);
                }
                int prv = -1;
                for(int i = 0; i <= 10; i++) {
                    int el = smallranks[i];
                    if(el == pos) {
                        if(i != smallranks.size()-1) {
                            arr[el] = arr[smallranks[i+1]]+1;
                        } else {
                            arr[el] = arr[smallranks[i-1]]-1;
                        }
                        break;
                    }
                    arr[el]++;
                }
                leftind = A-1;
                rightind = A+1;
                for(int i = 1; i < n; i++) {
                    if(leftind == 0) {
                        ans[rightind] = i;
                        rightind++;
                        continue;
                    }
                    if(rightind == n+1) {
                        ans[leftind] = i;
                        leftind--;
                        continue;
                    }
                    if(arr[leftind] < arr[rightind]) {
                        ans[leftind] = i;
                        leftind--;
                        continue;
                    } else {
                        ans[rightind] = i;
                        rightind++;
                        continue;
                    }
                }
            }
        }
    }
    return 0;
}

Compilation message (stderr)

cake.cpp: In function 'int main()':
cake.cpp:133:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         if(i != smallranks.size()-1) {
                            ~~^~~~~~~~~~~~~~~~~~~~~~
cake.cpp:129:21: warning: unused variable 'prv' [-Wunused-variable]
                 int prv = -1;
                     ^~~
cake.cpp:214:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         if(i != smallranks.size()-1) {
                            ~~^~~~~~~~~~~~~~~~~~~~~~
cake.cpp:210:21: warning: unused variable 'prv' [-Wunused-variable]
                 int prv = -1;
                     ^~~

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 0 / 50