| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 101550 |
2019-03-19T04:08:45 Z |
dantoh000 |
Cake (CEOI14_cake) |
C++14 |
|
648 ms |
8244 KB |
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
int main(){
int n,a;
scanf("%d%d",&n,&a);
a--;
ii d[n];
for (int i = 0; i < n; i++) {
scanf("%d",&d[i].first);
d[i].second = i;
//printf("order %d %d\n",d[i].first,d[i].second);
}
int q;
scanf("%d",&q);
int num0 = 0, num1 = 0;
iii qu[q];
for (int i = 0; i < q; i++){
char x;
scanf(" %c",&x);
qu[i].first = x != 'E';
if (x == 'E'){
num0++;
scanf("%d%d",&qu[i].second.first,&qu[i].second.second);
qu[i].second.first--;
}
else{
num1++;
scanf("%d",&qu[i].second.first);
qu[i].second.first--;
}
}
if (num0 <= 100){
int r[n];
sort(d,d+n,greater<ii>());
for (int i = 0; i < n; i++){
// printf("%d %d\n",d[i].first,d[i].second);
r[d[i].second] = i;
//printf("%d (%d) is the %dth delicious\n",d[i].second,d[i].first,i);
}
int ans[n]; memset(ans,0,sizeof(ans));
int vis[n]; memset(vis,0,sizeof(vis));
int ct = 0;
priority_queue<ii> pq; pq.push(ii(r[a],a));
while (pq.size()){
ii cur = pq.top(); pq.pop();
int t = cur.second;
//printf("now at %d %d\n",r[t],t);
ans[t] = ct++;
vis[t] = 1;
if (t-1 >= 0 && !vis[t-1]) {
pq.push(ii(r[t-1],t-1));
//printf("pushing %d %d\n",r[t-1],t-1);
}
if (t+1 < n && !vis[t+1]) {
pq.push(ii(r[t+1],t+1));
//printf("pushing %d %d\n",r[t+1],t+1);
}
}
for (int i = 0; i < q; i++){
if (qu[i].first == 0){
int k = qu[i].second.first, e = qu[i].second.second;
for (int i = 0; i < n; i++){
if (e <= r[i] && r[i] <= r[k]) r[i]++;
}
r[k] = e;
memset(vis,0,sizeof(vis));
memset(ans,0,sizeof(ans));
ct = 0;
pq.push(ii(r[a],a));
while (pq.size()){
ii cur = pq.top(); pq.pop();
int t = cur.second;
//printf("now at %d %d\n",r[t],t);
ans[t] = ct++;
vis[t] = 1;
if (t-1 >= 0 && !vis[t-1]) {
pq.push(ii(r[t-1],t-1));
//printf("pushing %d %d\n",r[t-1],t-1);
}
if (t+1 < n && !vis[t+1]) {
pq.push(ii(r[t+1],t+1));
//printf("pushing %d %d\n",r[t+1],t+1);
}
}
}
else{
int b = qu[i].second.first;
printf("%d\n",ans[b]);
}
}
}
else if (n <= 10000 && q <= 10000){
//printf("crab 1\n");
int r[n];
sort(d,d+n,greater<ii>());
for (int i = 0; i < n; i++){
//printf("%d %d\n",d[i].first,d[i].second);
r[d[i].second] = i;
//printf("%d is the %dth delicious\n",d[i].second,i);
}
//for (int i = 0; i < n; i++){
//printf("%d ",r[i],i);
//}
//printf("\n");
int ans = 0;
priority_queue<ii> pq;
int vis[n]; memset(vis,0,sizeof(vis));
for (int i = 0; i < q; i++){
//printf("%d %d %d\n",qu[i].first,qu[i].second.first,qu[i].second.second);
if (qu[i].first == 0){
int k = qu[i].second.first, e = qu[i].second.second;
for (int i = 0; i < n; i++){
if (e <= r[i] && r[i] <= r[k]) r[i]++;
}
r[k] = e;
}
else{
int b = qu[i].second.first;
memset(vis,0,sizeof(vis));
ans = 0;
pq.push(ii(r[a],a));
while (pq.size()){
ii cur = pq.top(); pq.pop();
int t = cur.second;
if (t == b) break;
//printf("now at %d %d\n",r[t],t);
ans++;
vis[t] = 1;
if (t-1 >= 0 && !vis[t-1]) {
pq.push(ii(r[t-1],t-1));
//printf("pushing %d %d\n",r[t-1],t-1);
}
if (t+1 < n && !vis[t+1]) {
pq.push(ii(r[t+1],t+1));
//printf("pushing %d %d\n",r[t+1],t+1);
}
}
printf("%d\n",ans);
while (pq.size()) pq.pop();
}
}
}
}
/*
5 3
5 1 2 4 3
17
F 1
F 2
F 3
F 4
F 5
E 2 1
F 1
F 2
F 3
F 4
F 5
E 5 2
F 1
F 2
F 3
F 4
F 5
*/
/*
4
1
0
2
3
4
3
0
1
2
4
3
0
1
2
*/
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:7:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&a);
~~~~~^~~~~~~~~~~~~~
cake.cpp:11:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&d[i].first);
~~~~~^~~~~~~~~~~~~~~~~~
cake.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&q);
~~~~~^~~~~~~~~
cake.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c",&x);
~~~~~^~~~~~~~~~
cake.cpp:25:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&qu[i].second.first,&qu[i].second.second);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake.cpp:30:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&qu[i].second.first);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
122 ms |
6272 KB |
Output isn't correct |
| 2 |
Incorrect |
137 ms |
6272 KB |
Output isn't correct |
| 3 |
Incorrect |
106 ms |
6272 KB |
Output isn't correct |
| 4 |
Incorrect |
110 ms |
6272 KB |
Output isn't correct |
| 5 |
Incorrect |
131 ms |
6372 KB |
Output isn't correct |
| 6 |
Incorrect |
126 ms |
6400 KB |
Output isn't correct |
| 7 |
Incorrect |
142 ms |
6400 KB |
Output isn't correct |
| 8 |
Incorrect |
199 ms |
6400 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
277 ms |
4060 KB |
Output isn't correct |
| 2 |
Incorrect |
232 ms |
3944 KB |
Output isn't correct |
| 3 |
Incorrect |
238 ms |
3904 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 5 |
Incorrect |
617 ms |
7232 KB |
Output isn't correct |
| 6 |
Incorrect |
648 ms |
7112 KB |
Output isn't correct |
| 7 |
Incorrect |
544 ms |
6884 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
896 KB |
Output isn't correct |
| 2 |
Incorrect |
14 ms |
896 KB |
Output isn't correct |
| 3 |
Incorrect |
40 ms |
1536 KB |
Output isn't correct |
| 4 |
Incorrect |
32 ms |
1664 KB |
Output isn't correct |
| 5 |
Incorrect |
48 ms |
2048 KB |
Output isn't correct |
| 6 |
Incorrect |
51 ms |
2560 KB |
Output isn't correct |
| 7 |
Incorrect |
68 ms |
2688 KB |
Output isn't correct |
| 8 |
Incorrect |
108 ms |
3456 KB |
Output isn't correct |
| 9 |
Incorrect |
174 ms |
8244 KB |
Output isn't correct |
| 10 |
Incorrect |
113 ms |
6172 KB |
Output isn't correct |
| 11 |
Incorrect |
126 ms |
6272 KB |
Output isn't correct |
| 12 |
Incorrect |
150 ms |
7800 KB |
Output isn't correct |
| 13 |
Incorrect |
152 ms |
8156 KB |
Output isn't correct |
