oj.uz

답안 #101550

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
101550 2019-03-19T04:08:45 Z dantoh000 케이크 (CEOI14_cake) C++14
0 / 100
 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);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 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

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 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

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 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