| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 131890 |
2019-07-17T21:56:53 Z |
bogdan10bos |
Cake (CEOI14_cake) |
C++14 |
|
2 ms |
380 KB |
/// Ce plm inseamna "acasa"? (nu buc in plm)
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int NMAX = 250005;
int N, A;
int pos[15];
class SegmentTree
{
public:
int ans, pp;
int aint[4 * NMAX], add[4 * NMAX], pos[4 * NMAX];
void lazy(int nod, int st, int mij, int dr)
{
if(add[nod] == 0) return;
aint[nod * 2] += add[nod];
aint[nod * 2 + 1] += add[nod];
add[nod * 2] += add[nod];
add[nod * 2 + 1] += add[nod];
add[nod] = 0;
}
void U(int nod, int st, int dr, int pp, int val)
{
if(st == dr)
{
aint[nod] = val;
add[nod] = 0;
pos[nod] = st;
return;
}
int mij = st + (dr - st) / 2;
lazy(nod, st, mij, dr);
if(pp <= mij) U(nod * 2, st, mij, pp, val);
else U(nod * 2 + 1, mij + 1, dr, pp, val);
aint[nod] = min(aint[nod * 2], aint[nod * 2 + 1]);
if(aint[nod] == aint[nod * 2]) pos[nod] = pos[nod * 2];
else pos[nod] = pos[nod * 2 + 1];
}
void U(int nod, int st, int dr, int sti, int dri, int val)
{
if(sti <= st && dr <= dri)
{
aint[nod] += val;
add[nod] += val;
return;
}
int mij = st + (dr - st) / 2;
lazy(nod, st, mij, dr);
if(sti <= mij) U(nod * 2, st, mij, sti, dri, val);
if(mij < dri) U(nod * 2 + 1, mij + 1, dr, sti, dri, val);
aint[nod] = min(aint[nod * 2], aint[nod * 2 + 1]);
if(aint[nod] == aint[nod * 2]) pos[nod] = pos[nod * 2];
else pos[nod] = pos[nod * 2 + 1];
}
void Q(int nod, int st, int dr, int sti, int dri)
{
if(sti <= st && dr <= dri)
{
if(ans > aint[nod])
{
ans = aint[nod];
pp = pos[nod];
}
return;
}
int mij = st + (dr - st) / 2;
lazy(nod, st, mij, dr);
if(sti <= mij) Q(nod * 2, st, mij, sti, dri);
if(mij < dri) Q(nod * 2 + 1, mij + 1, dr, sti, dri);
}
int query(int st, int dr)
{
if(st > dr) return st;
ans = 1 << 30;
pp = -1;
Q(1, 1, N, st, dr);
return pp;
}
int qmin(int st, int dr)
{
if(st > dr) return (1 << 30);
ans = 1 << 30;
pp = -1;
Q(1, 1, N, st, dr);
return ans;
}
}aint;
void solve(int p)
{
if(p == A)
{
printf("0\n");
return;
}
int P = p;
if(p < A)
{
int myp = aint.query(P, A - 1);
int val = aint.qmin(myp, myp);
int p = A + 1, u = N;
int pp = A;
while(p <= u)
{
int mij = p + (u - p) / 2;
int q = aint.qmin(A + 1, mij);
if(q > val)
{
pp = mij;
p = mij + 1;
}
else
u = mij - 1;
}
int ans = pp - P;
printf("%d\n", ans);
return;
}
if(p > A)
{
int myp = aint.query(A + 1, P);
int val = aint.qmin(myp, myp);
int p = 1, u = A - 1;
int pp = A;
while(p <= u)
{
int mij = p + (u - p) / 2;
int q = aint.qmin(mij, A - 1);
if(q > val)
{
pp = mij;
u = mij - 1;
}
else
p = mij + 1;
}
int ans = P - pp;
printf("%d\n", ans);
return;
}
}
int main()
{
freopen("1.in", "r", stdin);
scanf("%d%d", &N, &A);
for(int i = 1; i <= N; i++)
{
int x;
scanf("%d", &x);
x = N - x + 1;
if(x <= 10) pos[x] = i;
aint.U(1, 1, N, i, x);
}
int Q;
scanf("%d", &Q);
for(int q = 1; q <= Q; q++)
{
char ch = getchar();
while(ch != 'F' && ch != 'E') ch = getchar();
if(ch == 'F')
{
int p;
scanf("%d", &p);
solve(p);
}
else if(ch == 'E')
{
int p, e;
scanf("%d%d", &p, &e);
int nowp = 11;
for(int i = 1; i <= 10; i++)
if(pos[i] == p) nowp = i;
if(nowp == 11) aint.U(1, 1, N, 1, N, 1), nowp = 10;
for(int i = nowp; i > e; i--) pos[i] = pos[i - 1];
pos[e] = p;
for(int i = 1; i <= 10 && i <= N; i++)
aint.U(1, 1, N, pos[i], i);
}
}
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:166:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("1.in", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~
cake.cpp:167: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:171:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
~~~~~^~~~~~~~~~
cake.cpp:177:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &Q);
~~~~~^~~~~~~~~~
cake.cpp:186:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &p);
~~~~~^~~~~~~~~~
cake.cpp:192:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &p, &e);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 3 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 5 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 6 |
Incorrect |
2 ms |
380 KB |
Output isn't correct |
| 7 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 8 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 3 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 5 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 6 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 7 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 3 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 5 |
Incorrect |
2 ms |
380 KB |
Output isn't correct |
| 6 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 7 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 8 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 9 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 10 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 11 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 12 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 13 |
Incorrect |
2 ms |
380 KB |
Output isn't correct |
