| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 101559 |
2019-03-19T04:24:14 Z |
dwsc |
Cake (CEOI14_cake) |
C++14 |
|
47 ms |
23928 KB |
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
struct node{
int s,e,m;
int v;
node *l,*r;
node(int _s,int _e){
s = _s;
e = _e;
m = (s+e)/2;
v = 0;
if (s != e){
l = new node(s,m);
r = new node(m+1,e);
}
}
void up(int x,int v1){
if (s == e){
v = v1;
return;
}
if (x <= m) l->up(x,v1);
else r ->up(x,v1);
v = max(l->v,r->v);
}
int rmq(int x,int y){
if (s == x && e == y) return v;
if (y <= m) return l->rmq(x,y);
if (x > m) return r->rmq(x,y);
return max(l->rmq(x,y),r->rmq(x,y));
}
}*root;
int main(){
ios_base::sync_with_stdio(false);
int n,a,q;
cin >> n >>a;
a--;
root = new node(0,n-1);
if (n <= 25000){
int arr[n];
set<ii> s;
for (int i = 0; i < n; i++){
cin >> arr[i];
s.insert(ii(arr[i],i));
if (s.size() > 10) s.erase(s.begin());
root->up(i,arr[i]);
}
int q;
cin >> q;
vector<ii> del;
for (auto it = s.begin(); it != s.end(); ++it){
del.push_back(*it);
//cout << (*it).first << " " << (*it).second << "\n";
}
for (int i = 0; i < q; i++){
char c;
cin >> c;
if (c == 'E'){
int x,k;
cin >> x >> k;
x--;
set<ii> s2;
for (int j = del.size()-1; j >= 0; j--){
if (del.size()-j < k){
s2.insert(ii(del[j].first+1,del[j].second));
root->up(del[j].second,del[j].first+1);
}
else{
if (del[j].second != x)s2.insert(ii(del[j].first,del[j].second));
}
if (del.size()-j==k){
s2.insert(ii(del[j].first+1,x));
root->up(x,del[j].first+1);
}
if (s2.size() >= 10) s2.erase(s2.begin());
}
del.clear();
for (auto it = s2.begin(); it != s2.end(); ++it){
del.push_back(*it);
//cout << (*it).first << " " << (*it).second << "\n";
}
}
else{
int b;
cin >> b;
b--;
if (a == b) cout << "0\n";
else if (a < b){
continue;
int maxi = root->rmq(a+1,b);
int l = 0, r = a;
int ans = -1;
while (l != r){
int m = (l+r)/2;
if (root->rmq(m,a-1) > maxi){
ans = m;
l = m+1;
}
else r = m;
}
ans++;
cout << b-ans << "\n";
}
else{
int maxi = root->rmq(b,a-1);
int l = a+1, r = n;
while (l != r){
int m = (l+r)/2;
if (root->rmq(a+1,m) > maxi){
r = m;
}
else l = m+1;
}
l--;
cout << l-b << "\n";
}
}
}
}
else{
}
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:65:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (del.size()-j < k){
~~~~~~~~~~~~~^~~
cake.cpp:72:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (del.size()-j==k){
~~~~~~~~~~~~^~~
cake.cpp:36:13: warning: unused variable 'q' [-Wunused-variable]
int n,a,q;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
2304 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
10 ms |
2560 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
15 ms |
2560 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
8 ms |
2560 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
31 ms |
5496 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
25 ms |
5468 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
30 ms |
5368 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
20 ms |
5504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
9716 KB |
Output isn't correct |
| 2 |
Incorrect |
19 ms |
9720 KB |
Output isn't correct |
| 3 |
Incorrect |
15 ms |
9728 KB |
Output isn't correct |
| 4 |
Runtime error |
3 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Incorrect |
35 ms |
23804 KB |
Output isn't correct |
| 6 |
Incorrect |
38 ms |
23800 KB |
Output isn't correct |
| 7 |
Incorrect |
35 ms |
23928 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
1024 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
6 ms |
1536 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Incorrect |
9 ms |
5120 KB |
Output isn't correct |
| 4 |
Incorrect |
11 ms |
4992 KB |
Output isn't correct |
| 5 |
Runtime error |
4 ms |
896 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Incorrect |
10 ms |
6528 KB |
Output isn't correct |
| 7 |
Runtime error |
8 ms |
2560 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Incorrect |
15 ms |
9728 KB |
Output isn't correct |
| 9 |
Incorrect |
47 ms |
23800 KB |
Output isn't correct |
| 10 |
Runtime error |
5 ms |
896 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
13 ms |
4352 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Incorrect |
29 ms |
19164 KB |
Output isn't correct |
| 13 |
Incorrect |
42 ms |
23928 KB |
Output isn't correct |
