oj.uz

Submission #101553

# Submission time Handle Problem Language Result Execution time Memory
101553 2019-03-19T04:12:40 Z dantoh000 Cake (CEOI14_cake) C++14
0 / 100
 681 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;
    }
    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){
        int r[n];
        sort(d,d+n,greater<ii>());
        for (int i = 0; i < n; i++) r[d[i].second] = i;
        int ans = 0;
        priority_queue<ii> pq;
        int vis[n]; memset(vis,0,sizeof(vis));
        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;
            }
            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;
                    ans++;
                    vis[t] = 1;
                    if (t-1 >= 0 && !vis[t-1]) {
                        pq.push(ii(r[t-1],t-1));
                    }
                    if (t+1 < n && !vis[t+1]) {
                        pq.push(ii(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++){
            r[d[i].second] = 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;
            ans[t] = ct++;
            vis[t] = 1;
            if (t-1 >= 0 && !vis[t-1]) {
                pq.push(ii(r[t-1],t-1));
            }
            if (t+1 < n && !vis[t+1]) {
                pq.push(ii(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;
                    ans[t] = ct++;
                    vis[t] = 1;
                    if (t-1 >= 0 && !vis[t-1]) {
                        pq.push(ii(r[t-1],t-1));
                    }
                    if (t+1 < n && !vis[t+1]) {
                        pq.push(ii(r[t+1],t+1));
                    }
                }
            }
            else{
                int b = qu[i].second.first;
                printf("%d\n",ans[b]);
            }
        }
    }
}

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:15:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
     ~~~~~^~~~~~~~~
cake.cpp:20:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c",&x);
         ~~~~~^~~~~~~~~~
cake.cpp:24: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:29: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

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 138 ms 6272 KB Output isn't correct
2 Incorrect 132 ms 6272 KB Output isn't correct
3 Incorrect 117 ms 6272 KB Output isn't correct
4 Incorrect 127 ms 6272 KB Output isn't correct
5 Incorrect 147 ms 6400 KB Output isn't correct
6 Incorrect 132 ms 6400 KB Output isn't correct
7 Incorrect 128 ms 6400 KB Output isn't correct
8 Incorrect 162 ms 6400 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 302 ms 3960 KB Output isn't correct
2 Incorrect 256 ms 3960 KB Output isn't correct
3 Incorrect 252 ms 3960 KB Output isn't correct
4 Incorrect 2 ms 384 KB Output isn't correct
5 Incorrect 590 ms 7160 KB Output isn't correct
6 Incorrect 681 ms 7160 KB Output isn't correct
7 Incorrect 556 ms 6980 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 972 KB Output isn't correct
2 Incorrect 13 ms 896 KB Output isn't correct
3 Incorrect 36 ms 1536 KB Output isn't correct
4 Incorrect 26 ms 1536 KB Output isn't correct
5 Incorrect 38 ms 2048 KB Output isn't correct
6 Incorrect 46 ms 2552 KB Output isn't correct
7 Incorrect 77 ms 2816 KB Output isn't correct
8 Incorrect 68 ms 3584 KB Output isn't correct
9 Incorrect 172 ms 8184 KB Output isn't correct
10 Incorrect 111 ms 6272 KB Output isn't correct
11 Incorrect 113 ms 6272 KB Output isn't correct
12 Incorrect 150 ms 7676 KB Output isn't correct
13 Incorrect 171 ms 8072 KB Output isn't correct