| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 84044 |
2018-11-12T13:39:11 Z |
aminra |
Cake (CEOI14_cake) |
C++17 |
|
1591 ms |
6476 KB |
#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()
{
//you think I'm wat? coding machine?
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(1, n - 9); i--)
gre.insert({i, pos[i]});
cin >> q;
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();
vector<pair<int, int> > lrg;
for (auto u : gre)
lrg.push_back(u);
int cur = lrg[lrg.size() - val - 1].first + 1;
update(1, 0, n, idx, cur);
int tmp = cur;
it--;
vector< pair<int, int> > changes, del;
for (int j = lrg.size() - val; j < lrg.size(); j++)
{
if(lrg[j].first == cur)
changes.push_back({++cur, lrg[j].second}), del.push_back({cur - 1, lrg[j].second});
it--;
}
for (auto u : del)
gre.erase(u);
for (auto u : changes)
{
update(1, 0, n, u.second, u.first);
gre.insert(u);
}
gre.insert({tmp, idx});
if(gre.size() > 10)
{
pair<int, int> beg = *gre.begin();
gre.erase(beg);
}
/*for (int j = 0; j < n; j++)
cout << get(1, 0, n, j, j + 1) << " ";
cout << endl;*/
}
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 - 1 << "\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 - 1 << "\n";
}
}
}
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:79:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = lrg.size() - val; j < lrg.size(); j++)
~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
705 ms |
680 KB |
Output isn't correct |
| 2 |
Incorrect |
496 ms |
688 KB |
Output isn't correct |
| 3 |
Correct |
528 ms |
688 KB |
Output is correct |
| 4 |
Correct |
546 ms |
820 KB |
Output is correct |
| 5 |
Incorrect |
759 ms |
1096 KB |
Output isn't correct |
| 6 |
Incorrect |
664 ms |
1096 KB |
Output isn't correct |
| 7 |
Correct |
566 ms |
1096 KB |
Output is correct |
| 8 |
Correct |
439 ms |
1140 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
385 ms |
2980 KB |
Output is correct |
| 2 |
Incorrect |
280 ms |
2980 KB |
Output isn't correct |
| 3 |
Incorrect |
291 ms |
2980 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
2980 KB |
Output isn't correct |
| 5 |
Correct |
403 ms |
5412 KB |
Output is correct |
| 6 |
Incorrect |
455 ms |
5412 KB |
Output isn't correct |
| 7 |
Incorrect |
433 ms |
5496 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
104 ms |
5496 KB |
Output isn't correct |
| 2 |
Incorrect |
83 ms |
5496 KB |
Output isn't correct |
| 3 |
Incorrect |
178 ms |
5496 KB |
Output isn't correct |
| 4 |
Incorrect |
205 ms |
5496 KB |
Output isn't correct |
| 5 |
Incorrect |
272 ms |
5496 KB |
Output isn't correct |
| 6 |
Incorrect |
333 ms |
5496 KB |
Output isn't correct |
| 7 |
Incorrect |
315 ms |
5496 KB |
Output isn't correct |
| 8 |
Correct |
240 ms |
5496 KB |
Output is correct |
| 9 |
Incorrect |
1591 ms |
6396 KB |
Output isn't correct |
| 10 |
Incorrect |
882 ms |
6396 KB |
Output isn't correct |
| 11 |
Incorrect |
1134 ms |
6396 KB |
Output isn't correct |
| 12 |
Correct |
1584 ms |
6396 KB |
Output is correct |
| 13 |
Incorrect |
1551 ms |
6476 KB |
Output isn't correct |
