# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
62741 |
2018-07-30T00:13:33 Z |
MatheusLealV |
Cake (CEOI14_cake) |
C++17 |
|
2000 ms |
14604 KB |
#include <bits/stdc++.h>
#define l (2*nod)
#define r (2*nod + 1)
#define mid ((a + b)/2)
#define N 250050
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;
int n, q, a, v[N], dx[N], soma, tree[4*N];
vector<int> best;
vector<pii> ini;
void upd(int nod, int a, int b, int i, int x)
{
if(a == b) tree[nod] = x;
else
{
if(i <= mid) upd(l, a, mid, i, x);
else upd(r, mid + 1, b, i, x);
tree[nod] = max(tree[l], tree[r]);
}
}
int query(int nod, int a, int b, int i, int j)
{
if(j < a or i > b) return 0;
if(i <= a and j >= b) return tree[nod];
return max(query(l, a, mid, i, j), query(r, mid + 1, b, i, j));
}
int findR(int nod, int a, int b, int i, int val)
{
if(tree[nod] <= val or b <= i) return -1;
if(a == b) return a;
if(tree[l] > val)
{
int k = findR(l, a, mid, i, val);
if(k >= 0) return k;
}
return findR(r, mid + 1, b, i, val);
}
int findL(int nod, int a, int b, int i, int val)
{
if(tree[nod] <= val or a >= i) return -1;
if(a == b) return a;
if(tree[r] > val)
{
int k = findL(r, mid + 1, b, i, val);
if(k >= 0) return k;
}
return findL(l, a, mid, i, val);
}
void add(int x, int k)
{
vector<int> aux;
int id = 0;
for(int i = 0; ;i++)
{
id = i;
if(aux.size() == k - 1 or i >= best.size()) break;
if(best[i] != x) aux.push_back(best[i]);
}
aux.push_back(x);
for(int j = id; j < min(15, (int)best.size()); j++)
if(best[j] != x) aux.push_back(best[j]);
best = aux;
for(int i = best.size() - 2; i >= 0; i--)
{
dx[best[i]] = dx[best[i + 1]] + 1;
upd(1, 0, n, best[i], dx[best[i]]);
}
}
void print()
{
for(auto x: best) cout<<x<<" ";
cout<<"\n";
}
int main()
{
//ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>a;
for(int i = 1; i <= n; i++)
{
cin>>v[i];
ini.push_back({-v[i], i}), dx[i] = v[i];
upd(1, 0, n, i, v[i]);
}
sort(ini.begin(), ini.end());
for(int i = 0; i < min(15, (int) ini.size()); i++) best.push_back(ini[i].s);
best.push_back(0);
cin>>q;
for(int i = 0; i < q; i++)
{
char c; int x, y;
cin>>c>>x;
if(c == 'E')
{
cin>>y;
add(x, y);
}
else
{
if(a == x)
{
cout<<"0\n";
continue;
}
if(x < a)
{
int maior = query(1, 0, n, x, a - 1);
int R = findR(1, 0, n, a, maior);
if(R == -1) R = n + 1;
int ans = (a - x) + (R - a) - 1;
cout<<ans<<"\n";
}
else
{
int ans = x - a;
int maior = query(1, 0, n, a + 1, x);
for(int j = a - 1; j >= 1; j--)
{
if(dx[j] > maior) break;
ans ++;
}
cout<<ans<<"\n";
}
}
}
}
Compilation message
cake.cpp: In function 'void add(int, int)':
cake.cpp:82:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(aux.size() == k - 1 or i >= best.size()) break;
~~~~~~~~~~~^~~~~~~~
cake.cpp:82:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(aux.size() == k - 1 or i >= best.size()) break;
~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
248 KB |
Output is correct |
2 |
Correct |
4 ms |
360 KB |
Output is correct |
3 |
Correct |
4 ms |
568 KB |
Output is correct |
4 |
Correct |
19 ms |
656 KB |
Output is correct |
5 |
Correct |
61 ms |
1132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1386 ms |
4744 KB |
Output is correct |
2 |
Correct |
1207 ms |
4776 KB |
Output is correct |
3 |
Correct |
1262 ms |
4848 KB |
Output is correct |
4 |
Correct |
1233 ms |
4848 KB |
Output is correct |
5 |
Correct |
1206 ms |
5216 KB |
Output is correct |
6 |
Correct |
1261 ms |
5216 KB |
Output is correct |
7 |
Correct |
1311 ms |
5216 KB |
Output is correct |
8 |
Correct |
1145 ms |
5308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
861 ms |
8036 KB |
Output is correct |
2 |
Correct |
1265 ms |
8036 KB |
Output is correct |
3 |
Correct |
868 ms |
8080 KB |
Output is correct |
4 |
Correct |
3 ms |
8080 KB |
Output is correct |
5 |
Execution timed out |
2051 ms |
11356 KB |
Time limit exceeded |
6 |
Correct |
714 ms |
12388 KB |
Output is correct |
7 |
Execution timed out |
2039 ms |
12388 KB |
Time limit exceeded |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
178 ms |
12388 KB |
Output is correct |
2 |
Correct |
168 ms |
12388 KB |
Output is correct |
3 |
Correct |
572 ms |
12388 KB |
Output is correct |
4 |
Correct |
633 ms |
12388 KB |
Output is correct |
5 |
Correct |
551 ms |
12388 KB |
Output is correct |
6 |
Correct |
661 ms |
12388 KB |
Output is correct |
7 |
Correct |
635 ms |
12388 KB |
Output is correct |
8 |
Correct |
746 ms |
12388 KB |
Output is correct |
9 |
Execution timed out |
2051 ms |
12976 KB |
Time limit exceeded |
10 |
Correct |
1159 ms |
12976 KB |
Output is correct |
11 |
Correct |
1360 ms |
12976 KB |
Output is correct |
12 |
Execution timed out |
2069 ms |
13796 KB |
Time limit exceeded |
13 |
Execution timed out |
2059 ms |
14604 KB |
Time limit exceeded |