#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int infint = 1e9;
const int MOD = (int)1e9 + 7;
const int MAXN = (int)250003;
int n, s, q, a[MAXN], seg[4 * MAXN], pos[MAXN];
void build(int node, int st, int en)
{
if(en - st < 2)
{
seg[node] = a[st];
return;
}
int mid = (st + en) >> 1;
build(node << 1, st, mid);
build(node << 1 | 1, mid, en);
seg[node] = max(seg[node << 1], seg[node << 1 | 1]);
}
void update(int node, int st, int en, int idx, int val)
{
if(en - st < 2)
{
seg[node] = val;
return;
}
int mid = (st + en) >> 1;
if(idx < mid)
update(node << 1, st, mid, idx, val);
else
update(node << 1 | 1, mid, en, idx, val);
seg[node] = max(seg[node << 1], seg[node << 1 | 1]);
}
int get(int node, int st, int en, int l, int r)
{
if(l >= en || st >= r)
return 0;
if(l <= st && en <= r)
return seg[node];
int mid = (st + en) >> 1;
return max(get(node << 1, st, mid, l, r), get(node << 1 | 1, mid, en, l, r));
}
set< pair<int, int> > gre;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> s;
s--;
for (int i = 0; i < n; i++)
{
cin >> a[i];
pos[a[i]] = i;
}
build(1, 0, n);
for (int i = n; i >= max(0, n - 9); i--)
gre.insert({i, pos[i]});
for (int i = 0; i < q; i++)
{
char type;
cin >> type;
if(type == 'E')
{
int idx, val;
cin >> idx >> val;
idx--, val--;
auto it = gre.rbegin();
for (int j = 0; j < val; j--)
it--;
int cur = (*it).first + 1;
update(1, 0, n, idx, cur);
int tmp = cur;
it++;
vector< pair<int, int> > changes, del;
for (int j = 0; j < val; j++)
{
if((*it).first == cur)
changes.push_back({(*it).second, ++cur}), del.push_back({(*it).second, cur - 1});
it++;
}
for (auto u : del)
gre.erase(u);
for (auto u : changes)
{
update(1, 0, n, u.first, u.second);
gre.insert(u);
}
gre.insert({idx, tmp});
if(gre.size() > 10)
{
pair<int, int> beg = *gre.begin();
gre.erase(beg);
}
}
else
{
int idx;
cin >> idx;
idx--;
if(idx == s)
{
cout << 0 << "\n";
continue;
}
if(idx < s)
{
int mx = get(1, 0, n, idx, s + 1);
int L = s - 1, R = n;
while(R - L > 1)
{
int mid = (L + R) >> 1;
if(get(1, 0, n, s, mid + 1) > mx)
R = mid;
else
L = mid;
}
cout << R - idx << "\n";
}
else
{
int mx = get(1, 0, n, s, idx + 1);
int L = -1, R = s;
while(R - L > 1)
{
int mid = (L + R) >> 1;
if(get(1, 0, n, mid, s + 1) > mx)
L = mid;
else
R = mid;
}
cout << idx - L << "\n";
}
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
640 KB |
Output isn't correct |
2 |
Incorrect |
3 ms |
808 KB |
Output isn't correct |
3 |
Incorrect |
4 ms |
808 KB |
Output isn't correct |
4 |
Incorrect |
3 ms |
808 KB |
Output isn't correct |
5 |
Incorrect |
5 ms |
896 KB |
Output isn't correct |
6 |
Incorrect |
5 ms |
1004 KB |
Output isn't correct |
7 |
Incorrect |
5 ms |
1044 KB |
Output isn't correct |
8 |
Incorrect |
5 ms |
1044 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
18 ms |
2356 KB |
Output isn't correct |
2 |
Incorrect |
13 ms |
2356 KB |
Output isn't correct |
3 |
Incorrect |
13 ms |
2512 KB |
Output isn't correct |
4 |
Incorrect |
2 ms |
2512 KB |
Output isn't correct |
5 |
Incorrect |
40 ms |
4536 KB |
Output isn't correct |
6 |
Incorrect |
39 ms |
4576 KB |
Output isn't correct |
7 |
Incorrect |
31 ms |
4576 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
4576 KB |
Output isn't correct |
2 |
Incorrect |
3 ms |
4576 KB |
Output isn't correct |
3 |
Incorrect |
13 ms |
4576 KB |
Output isn't correct |
4 |
Incorrect |
8 ms |
4576 KB |
Output isn't correct |
5 |
Incorrect |
2 ms |
4576 KB |
Output isn't correct |
6 |
Incorrect |
10 ms |
4576 KB |
Output isn't correct |
7 |
Incorrect |
4 ms |
4576 KB |
Output isn't correct |
8 |
Incorrect |
15 ms |
4576 KB |
Output isn't correct |
9 |
Incorrect |
42 ms |
4604 KB |
Output isn't correct |
10 |
Incorrect |
2 ms |
4604 KB |
Output isn't correct |
11 |
Incorrect |
6 ms |
4604 KB |
Output isn't correct |
12 |
Incorrect |
30 ms |
4604 KB |
Output isn't correct |
13 |
Incorrect |
44 ms |
4604 KB |
Output isn't correct |