#include "bits/stdc++.h"
using namespace std;
const int inf = 1e9;
const int ts = 250001;
int d[250010];
int n, a;
vector <int> best;
int sz;
struct tree {
int t[250010 * 4];
void update(int x, int val, int c = 1, int b = 1, int e = ts) {
if(b == e) {
t[c] = val;
return ;
}
int m = (b + e) >> 1;
int l = c << 1;
int r = l + 1;
if(x <= m) update(x, val, l, b, m);
else update(x, val, r, m + 1, e);
t[c] = max(t[l], t[r]);
}
int query(int x, int y, int c = 1, int b = 1, int e = ts) {
if(x <= b && e <= y) return t[c];
if(y < b || e < x) return 0;
int m = (b + e) >> 1;
int l = c << 1;
int r = l + 1;
return max(query(x, y, l, b, m), query(x, y, r, m + 1, e));
}
int searchSuffix(int val, int c = 1, int b = 1, int e = ts) {
if(b == e) {
return t[c] > val ? b : 0;
}
int m = (b + e) >> 1;
int l = c << 1;
int r = l + 1;
if(t[r] > val) return searchSuffix(val, r, m + 1, e);
else return searchSuffix(val, l, b, m);
}
int searchPrefix(int val, int c = 1, int b = 1, int e = ts) {
if(b == e) {
return t[c] > val ? b : n+1;
}
int m = (b + e) >> 1;
int l = c << 1;
int r = l + 1;
if(t[l] > val) return searchPrefix(val, l, b, m);
else return searchPrefix(val, r, m + 1, e);
}
} P, S;
int query(int b) {
if(b == a) return 0;
if(b < a) {
int mx = P.query(b, a);
int idx = S.searchPrefix(mx);
return idx - b - 1;
} else {
int mx = S.query(a, b);
int idx = P.searchSuffix(mx);
return b - idx - 1;
}
}
bool cmp(int p, int q) {
return d[p] > d[q];
}
void update(int p, int q) {
--q;
int pos = find(best.begin(), best.end(), p) - best.begin();
while(pos < q) {
swap(d[best[pos]], d[best[pos + 1]]);
swap(best[pos], best[pos + 1]);
++pos;
}
while(pos > q) {
swap(d[best[pos]], d[best[pos - 1]]);
swap(best[pos], best[pos - 1]);
--pos;
}
for(int i = 0; i < best.size(); i++) {
if(best[i] == a) continue;
if(best[i] < a) {
P.update(best[i], d[best[i]]);
} else {
S.update(best[i], d[best[i]]);
}
}
}
int main(int argc, char const *argv[])
{
scanf("%d %d", &n, &a);
for(int i = 1; i <= n; i++) {
scanf("%d", &d[i]);
best.emplace_back(i);
}
sort(best.begin(), best.end(), cmp);
for(int i = a + 1; i <= n; i++) {
S.update(i, d[i]);
}
for(int i = 1; i < a; i++) {
P.update(i, d[i]);
}
int q;
scanf("%d", &q);
while(q--) {
char c;
int p, q;
scanf(" %c", &c);
if(c == 'F') {
scanf("%d", &p);
printf("%d\n", query(p));
} else {
scanf("%d %d", &p, &q);
update(p, q);
}
}
return 0;
}
Compilation message
cake.cpp: In function 'void update(int, int)':
cake.cpp:83:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < best.size(); i++) {
~~^~~~~~~~~~~~~
cake.cpp: In function 'int main(int, const char**)':
cake.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &a);
~~~~~^~~~~~~~~~~~~~~~~
cake.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &d[i]);
~~~~~^~~~~~~~~~~~~
cake.cpp:108:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
cake.cpp:112:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c", &c);
~~~~~^~~~~~~~~~~
cake.cpp:114:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &p);
~~~~~^~~~~~~~~~
cake.cpp:117:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &p, &q);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
3 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
195 ms |
608 KB |
Output is correct |
| 5 |
Execution timed out |
2035 ms |
764 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2017 ms |
640 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2045 ms |
640 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2056 ms |
640 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2021 ms |
640 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2012 ms |
1024 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2037 ms |
896 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2043 ms |
1024 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2049 ms |
1024 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1541 ms |
2936 KB |
Output is correct |
| 2 |
Correct |
739 ms |
2672 KB |
Output is correct |
| 3 |
Correct |
678 ms |
2672 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Execution timed out |
2021 ms |
5068 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2032 ms |
4848 KB |
Time limit exceeded |
| 7 |
Correct |
1592 ms |
5152 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2024 ms |
656 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2049 ms |
760 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2028 ms |
1404 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2099 ms |
1268 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2021 ms |
904 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2037 ms |
1648 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2033 ms |
760 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2066 ms |
2160 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2053 ms |
4588 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2032 ms |
880 KB |
Time limit exceeded |
| 11 |
Execution timed out |
2054 ms |
884 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2045 ms |
3836 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2051 ms |
4460 KB |
Time limit exceeded |
