#include<bits/stdc++.h>
using namespace std;
int splitPos, N, M, a[250009], stk[2][250009], sz[2];
int last, initInv[250009], nxt[250009], prv[250009];
void read ()
{
scanf ("%d %d", &N, &splitPos), M = N;
for (int i=1; i<=N; i++)
scanf ("%d", &a[i]), initInv[a[i]] = i;
for (int i=0; i<=N + 1; i++)
{
if (i > 0) prv[initInv[i]] = initInv[i - 1];
if (i <= N) nxt[initInv[i]] = initInv[i + 1];
}
last = initInv[N];
}
void del (int pos)
{
if (pos == 0) prv[nxt[pos]] = 0;
else
{
int x = prv[pos], y = nxt[pos];
nxt[x] = y, prv[y] = x;
}
}
void change (int P, int e)
{
del (P);
if (e == 1)
{
nxt[last] = P, prv[P] = last;
a[P] = a[last] + 1, last = P;
return ;
}
for (int i=last; e > 1; i = prv[i], e --)
a[i] ++, nxt[P] = i;
prv[P] = prv[nxt[P]];
nxt[prv[P]] = P;
prv[nxt[P]] = P;
a[P] = a[nxt[P]] - 1;
}
void buildStacks ()
{
for (int lin = 0; lin < 2; lin ++)
{
int bg = splitPos - 1, nd = 0, rat = -1;
if (lin == 1)
bg = splitPos + 1, nd = N + 1, rat = +1;
for (int i=bg; i != nd; i+=rat)
if (sz[lin] == 0 || a[stk[lin][sz[lin]]] < a[i])
stk[lin][++sz[lin]] = i;
}
}
void updateStack (int pos)
{
int lin = 0;
vector < int > currPos;
if (pos < splitPos)
{
while (sz[0] > 0 && stk[0][sz[0]] <= pos)
currPos.push_back (stk[0][sz[0] --]);
}
else
{
lin = 1;
while (sz[1] > 0 && stk[1][sz[1]] >= pos)
currPos.push_back (stk[1][sz[1] --]);
}
currPos.push_back (pos);
reverse (currPos.begin (), currPos.end ());
for (auto i : currPos)
if (sz[lin] == 0 || a[stk[lin][sz[lin]]] < a[i])
stk[lin][++sz[lin]] = i;
}
int countSmaller (int lin, int val)
{
int p = 1, u = sz[lin], mij, ras = (lin == 0 ? 0 : N + 1);
while (p <= u)
{
mij = (p + u) >> 1;
if (a[stk[lin][mij]] >= val) ras = stk[lin][mij], u = mij - 1;
else p = mij + 1;
}
if (lin == 1) ras = ras - splitPos - 1;
else ras = splitPos - ras - 1;
return ras;
}
int query (int pos)
{
if (pos == splitPos) return 0;
if (pos > splitPos)
{
int p = 2, u = sz[1], mij, ras = 1;
while (p <= u)
{
mij = (p + u) >> 1;
if (stk[1][mij] <= pos) ras = mij, p = mij + 1;
else u = mij - 1;
}
return pos - splitPos + countSmaller (0, a[stk[1][ras]]);
}
int p = 2, u = sz[0], mij, ras = 1;
while (p <= u)
{
mij = (p + u) >> 1;
if (stk[0][mij] >= pos) ras = mij, p = mij + 1;
else u = mij - 1;
}
return splitPos - pos + countSmaller (1, a[stk[0][ras]]);
}
int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);
read ();
buildStacks ();
int Q;
scanf ("%d\n", &Q);
while (Q --)
{
char type;
scanf ("%c ", &type);
if (type == 'E')
{
int p, e;
scanf ("%d %d\n", &p, &e);
change (p, e);
if (p != splitPos)
updateStack (p);
continue;
}
int pos;
scanf ("%d\n", &pos);
printf ("%d\n", query (pos));
}
return 0;
}
Compilation message
cake.cpp: In function 'void read()':
cake.cpp:10:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d %d", &N, &splitPos), M = N;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
cake.cpp:12:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &a[i]), initInv[a[i]] = i;
~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
cake.cpp: In function 'int main()':
cake.cpp:129:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d\n", &Q);
~~~~~~^~~~~~~~~~~~
cake.cpp:133:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%c ", &type);
~~~~~~^~~~~~~~~~~~~~
cake.cpp:137:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d %d\n", &p, &e);
~~~~~~^~~~~~~~~~~~~~~~~~~
cake.cpp:144:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d\n", &pos);
~~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
5 ms |
748 KB |
Output is correct |
| 5 |
Correct |
9 ms |
836 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
243 ms |
5296 KB |
Output is correct |
| 2 |
Correct |
226 ms |
9744 KB |
Output is correct |
| 3 |
Correct |
230 ms |
14412 KB |
Output is correct |
| 4 |
Correct |
225 ms |
18748 KB |
Output is correct |
| 5 |
Correct |
298 ms |
23680 KB |
Output is correct |
| 6 |
Correct |
223 ms |
28880 KB |
Output is correct |
| 7 |
Correct |
249 ms |
33728 KB |
Output is correct |
| 8 |
Correct |
207 ms |
38648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
41860 KB |
Output is correct |
| 2 |
Correct |
68 ms |
43004 KB |
Output is correct |
| 3 |
Correct |
54 ms |
44380 KB |
Output is correct |
| 4 |
Correct |
3 ms |
44380 KB |
Output is correct |
| 5 |
Correct |
101 ms |
49428 KB |
Output is correct |
| 6 |
Correct |
94 ms |
51796 KB |
Output is correct |
| 7 |
Correct |
73 ms |
54108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
54108 KB |
Output is correct |
| 2 |
Correct |
25 ms |
54108 KB |
Output is correct |
| 3 |
Correct |
48 ms |
54108 KB |
Output is correct |
| 4 |
Correct |
47 ms |
54108 KB |
Output is correct |
| 5 |
Correct |
66 ms |
54108 KB |
Output is correct |
| 6 |
Correct |
76 ms |
56640 KB |
Output is correct |
| 7 |
Correct |
84 ms |
57456 KB |
Output is correct |
| 8 |
Correct |
118 ms |
60940 KB |
Output is correct |
| 9 |
Correct |
355 ms |
71268 KB |
Output is correct |
| 10 |
Correct |
254 ms |
71268 KB |
Output is correct |
| 11 |
Correct |
349 ms |
75364 KB |
Output is correct |
| 12 |
Correct |
359 ms |
84448 KB |
Output is correct |
| 13 |
Correct |
315 ms |
91352 KB |
Output is correct |
