#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];
//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;*/
}
}
}
return 0;
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:132:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i != smallranks.size()-1) {
~~^~~~~~~~~~~~~~~~~~~~~~
cake.cpp:128:21: warning: unused variable 'prv' [-Wunused-variable]
int prv = -1;
^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
3 ms |
484 KB |
Output is correct |
3 |
Correct |
5 ms |
604 KB |
Output is correct |
4 |
Correct |
8 ms |
700 KB |
Output is correct |
5 |
Correct |
51 ms |
884 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
353 ms |
4724 KB |
Output is correct |
2 |
Correct |
276 ms |
4764 KB |
Output is correct |
3 |
Correct |
275 ms |
4768 KB |
Output is correct |
4 |
Correct |
394 ms |
4896 KB |
Output is correct |
5 |
Correct |
348 ms |
5024 KB |
Output is correct |
6 |
Correct |
335 ms |
5024 KB |
Output is correct |
7 |
Correct |
292 ms |
5024 KB |
Output is correct |
8 |
Correct |
394 ms |
5152 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
60 ms |
5152 KB |
Output isn't correct |
2 |
Incorrect |
56 ms |
5152 KB |
Output isn't correct |
3 |
Incorrect |
47 ms |
5152 KB |
Output isn't correct |
4 |
Correct |
3 ms |
5152 KB |
Output is correct |
5 |
Incorrect |
97 ms |
5152 KB |
Output isn't correct |
6 |
Incorrect |
104 ms |
5152 KB |
Output isn't correct |
7 |
Incorrect |
79 ms |
5152 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
18 ms |
5152 KB |
Output isn't correct |
2 |
Incorrect |
17 ms |
5152 KB |
Output isn't correct |
3 |
Incorrect |
27 ms |
5152 KB |
Output isn't correct |
4 |
Incorrect |
42 ms |
5152 KB |
Output isn't correct |
5 |
Incorrect |
30 ms |
5152 KB |
Output isn't correct |
6 |
Incorrect |
65 ms |
5152 KB |
Output isn't correct |
7 |
Incorrect |
50 ms |
5152 KB |
Output isn't correct |
8 |
Incorrect |
86 ms |
5152 KB |
Output isn't correct |
9 |
Incorrect |
167 ms |
7676 KB |
Output isn't correct |
10 |
Incorrect |
98 ms |
7676 KB |
Output isn't correct |
11 |
Incorrect |
101 ms |
7676 KB |
Output isn't correct |
12 |
Incorrect |
194 ms |
7676 KB |
Output isn't correct |
13 |
Incorrect |
198 ms |
7704 KB |
Output isn't correct |