oj.uz

답안 #842160

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
842160 2023-09-02T13:00:24 Z konber Exam (eJOI20_exam) C++14
12 / 100
 250 ms 4832 KB 
#include <iostream>
#include <vector>

using namespace std;

vector<int> A, b, st;
int N;

void build(int p, int L, int R){
    if(L==R){
        st[p] = A[L];
        return;
    }
    build(2*p, L, (L+R)/2);
    build(2*p+1, (L+R)/2+1, R);
    st[p] = max(st[2*p], st[2*p+1]);
}

int rmq(int p, int L, int R, int i, int j){
    if(j < L || i > R) return -1;
    if(L >= i && R <= j) return st[p];
    int mid=(L+R)/2;
    return max(rmq(2*p, L, mid, i, j), rmq(2*p+1, mid+1, R, i, j));
}

int f(vector<int> a, int i){
    if(i==N){
        int ans=0;
        for(int j=0; j < N; j++) ans += a[j]==b[j];
        return ans;
    }

    int j=i, k=i;
    bool changes=true;
    vector<int> a1=a, a2=a;
    while(changes){
        changes = false;
        if(j >= 0 && a[j] <= b[i]){
            a1[j] = b[i];
            changes=true;
            j--;
        }
        if(k <= N-1 && a[k] <= b[i]){
            a2[k] = b[i];
            changes=true;
            k++;
        }
        if(j==0 && k==N-1) break;
    }
    return max(f(a, i+1), max(f(a1, i+1), f(a2, i+1)));
}

int main()
{
    scanf("%d", &N);
    A.resize(N);
    b.resize(N);
    st.resize(4*N);
    for(int i=0; i < N; i++)
        scanf("%d", &A[i]);
    for(int i=0; i < N; i++)
        scanf("%d", &b[i]);

    if(N <= 10){
        cout << f(A, 0) << endl;
    }
    else{
        build(1, 0, N-1);
        int s=0, i=0;
        while(i < N){
            int first=i, last=N-1, ans=i, mid;
            while(first <= last){
                mid = (first+last)/2;
                int m = rmq(1, 0, N-1, i, mid);
                if(m > b[0]) last = mid-1;
                else{
                    ans = mid;
                    first = mid+1;
                }
            }
            if(rmq(1, 0, N-1, i, ans)==b[0]) s += ans-i+1;
            i = ans+1;
        }
        printf("%d\n", s);
    }
}

Compilation message

exam.cpp: In function 'int main()':
exam.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
exam.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         scanf("%d", &A[i]);
      |         ~~~~~^~~~~~~~~~~~~
exam.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         scanf("%d", &b[i]);
      |         ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 14.0

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

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 4 ms 1116 KB Output is correct
3 Correct 138 ms 3420 KB Output is correct
4 Correct 14 ms 3164 KB Output is correct
5 Correct 19 ms 4692 KB Output is correct
6 Correct 250 ms 3168 KB Output is correct
7 Correct 14 ms 3164 KB Output is correct
8 Correct 240 ms 4832 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 16.0

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

Subtask #6
0 / 22.0

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