oj.uz

답안 #101552

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
101552 2019-03-19T04:10:19 Z dantoh000 케이크 (CEOI14_cake) C++14
0 / 100
 666 ms 8184 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 (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
*/

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 128 ms 6272 KB Output isn't correct
2 Incorrect 162 ms 6272 KB Output isn't correct
3 Incorrect 141 ms 6272 KB Output isn't correct
4 Incorrect 111 ms 6244 KB Output isn't correct
5 Incorrect 157 ms 6400 KB Output isn't correct
6 Incorrect 155 ms 6372 KB Output isn't correct
7 Incorrect 147 ms 6364 KB Output isn't correct
8 Incorrect 144 ms 6400 KB Output isn't correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 311 ms 4112 KB Output isn't correct
2 Incorrect 305 ms 4004 KB Output isn't correct
3 Incorrect 261 ms 3948 KB Output isn't correct
4 Incorrect 2 ms 256 KB Output isn't correct
5 Incorrect 550 ms 7032 KB Output isn't correct
6 Incorrect 666 ms 7176 KB Output isn't correct
7 Incorrect 597 ms 6848 KB Output isn't correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 896 KB Output isn't correct
2 Incorrect 22 ms 896 KB Output isn't correct
3 Incorrect 28 ms 1536 KB Output isn't correct
4 Incorrect 25 ms 1536 KB Output isn't correct
5 Incorrect 58 ms 2048 KB Output isn't correct
6 Incorrect 61 ms 2560 KB Output isn't correct
7 Incorrect 50 ms 2688 KB Output isn't correct
8 Incorrect 67 ms 3456 KB Output isn't correct
9 Incorrect 161 ms 8056 KB Output isn't correct
10 Incorrect 190 ms 6244 KB Output isn't correct
11 Incorrect 120 ms 6400 KB Output isn't correct
12 Incorrect 244 ms 7676 KB Output isn't correct
13 Incorrect 243 ms 8184 KB Output isn't correct