Submission #842160

#	Time	Username	Problem	Language	Result	Execution time	Memory
842160		konber	Exam (eJOI20_exam)	C++14	12 / 100	250 ms	4832 KiB

exam

#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 (stderr)

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
• Subtask 2: 12 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 16
• Subtask 6: 0 / 22