제출 #101552

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
101552		dantoh000	케이크 (CEOI14_cake)	C++14	0 / 100	666 ms	8184 KiB

cake

#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 (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();
            }
        }
    }
    else 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]);
            }
        }
    }
}
/*
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
*/

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50