#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;
auto it = find(best.begin(), best.end(), p);
best.erase(it);
best.insert(best.begin() + q, p);
for(int i = 0; i < best.size(); i++) {
d[best[i]] = n - i;
}
for(int i = 0; i < best.size(); i++) {
// cout << best[i] << ' ' << d[best[i]] << endl;
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:76:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < best.size(); i++) {
~~^~~~~~~~~~~~~
cake.cpp:79: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:92: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:94:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &d[i]);
~~~~~^~~~~~~~~~~~~
cake.cpp:105:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
cake.cpp:109:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c", &c);
~~~~~^~~~~~~~~~~
cake.cpp:111:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &p);
~~~~~^~~~~~~~~~
cake.cpp:114: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 |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
3 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
428 KB |
Output is correct |
| 4 |
Correct |
210 ms |
384 KB |
Output is correct |
| 5 |
Execution timed out |
2027 ms |
768 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2040 ms |
640 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2041 ms |
640 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2047 ms |
512 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2037 ms |
768 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2028 ms |
1024 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2055 ms |
1024 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2029 ms |
1024 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2055 ms |
896 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1449 ms |
2892 KB |
Output is correct |
| 2 |
Correct |
787 ms |
2772 KB |
Output is correct |
| 3 |
Correct |
656 ms |
2672 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Execution timed out |
2005 ms |
5104 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2027 ms |
4944 KB |
Time limit exceeded |
| 7 |
Correct |
1610 ms |
5148 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2029 ms |
732 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2024 ms |
632 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2050 ms |
1404 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2045 ms |
1396 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2056 ms |
760 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2065 ms |
1656 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2069 ms |
760 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2052 ms |
2160 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2067 ms |
4608 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2057 ms |
632 KB |
Time limit exceeded |
| 11 |
Execution timed out |
2032 ms |
1020 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2049 ms |
3692 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2037 ms |
4588 KB |
Time limit exceeded |
