#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 {
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]++;
}
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;
}
}
}
}
}
return 0;
}
Compilation message
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:191:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i != smallranks.size()-1) {
~~^~~~~~~~~~~~~~~~~~~~~~
cake.cpp:187:21: warning: unused variable 'prv' [-Wunused-variable]
int prv = -1;
^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
436 KB |
Output is correct |
| 4 |
Correct |
10 ms |
696 KB |
Output is correct |
| 5 |
Correct |
45 ms |
748 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
292 ms |
4636 KB |
Output is correct |
| 2 |
Correct |
352 ms |
4636 KB |
Output is correct |
| 3 |
Correct |
284 ms |
4704 KB |
Output is correct |
| 4 |
Correct |
294 ms |
4708 KB |
Output is correct |
| 5 |
Correct |
293 ms |
4900 KB |
Output is correct |
| 6 |
Correct |
313 ms |
4900 KB |
Output is correct |
| 7 |
Correct |
329 ms |
4900 KB |
Output is correct |
| 8 |
Correct |
356 ms |
4988 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
72 ms |
4988 KB |
Output isn't correct |
| 2 |
Incorrect |
65 ms |
4988 KB |
Output isn't correct |
| 3 |
Incorrect |
55 ms |
4988 KB |
Output isn't correct |
| 4 |
Correct |
2 ms |
4988 KB |
Output is correct |
| 5 |
Incorrect |
135 ms |
5996 KB |
Output isn't correct |
| 6 |
Incorrect |
170 ms |
6044 KB |
Output isn't correct |
| 7 |
Incorrect |
115 ms |
6044 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
129 ms |
6044 KB |
Output isn't correct |
| 2 |
Correct |
292 ms |
6044 KB |
Output is correct |
| 3 |
Execution timed out |
2056 ms |
6044 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2025 ms |
6044 KB |
Time limit exceeded |
| 5 |
Incorrect |
297 ms |
6044 KB |
Output isn't correct |
| 6 |
Execution timed out |
2035 ms |
6044 KB |
Time limit exceeded |
| 7 |
Correct |
1366 ms |
6044 KB |
Output is correct |
| 8 |
Execution timed out |
2033 ms |
6044 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2032 ms |
8704 KB |
Time limit exceeded |
| 10 |
Correct |
1002 ms |
8704 KB |
Output is correct |
| 11 |
Execution timed out |
2025 ms |
8704 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2064 ms |
8704 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2070 ms |
8816 KB |
Time limit exceeded |
