oj.uz

Submission #412246

# Submission time Handle Problem Language Result Execution time Memory
412246 2021-05-26T15:59:08 Z Theo830 Exam (eJOI20_exam) C++17
100 / 100
 201 ms 98676 KB 
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
ll INF = 1e9+7;
ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ii,ll>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
ll seg[400005]={0};
void update(ll s,ll e,ll qs,ll qe,ll idx,ll k){
    if(s == e && s == qs){
        seg[idx] = max(seg[idx],k);
        return;
    }
    if(qs > e || qe < s){
        return;
    }
    ll mid = (s+e)/2;
    update(s,mid,qs,qe,idx*2,k);
    update(mid+1,e,qs,qe,idx*2+1,k);
    seg[idx] = max(seg[idx*2],seg[idx*2+1]);
}
ll query(ll s,ll e,ll qs,ll qe,ll idx){
    if(qs <= s && e <= qe){
        return seg[idx];
    }
    if(qs > e || qe < s){
        return 0;
    }
    ll mid = (s+e)/2;
    ll a = query(s,mid,qs,qe,idx*2);
    ll b = query(mid+1,e,qs,qe,idx*2+1);
    return max(a,b);
}
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin>>n;
    ll a[n],b[n];
    map<ll,ll>mp;
    map<ll,ll>pos;
    bool ok1 = 1,ok2 = 1;
    f(i,0,n){
        cin>>a[i];
        pos[a[i]] = i+1;
        if(mp[a[i]] == 1){
            ok1 = 0;
        }
        mp[a[i]]++;
    }
    f(i,0,n){
        cin>>b[i];
        if(b[i] != b[0]){
            ok2 = 0;
        }
        if(ok1){
            b[i] = pos[b[i]];
        }
        if(b[i] == 0){
            b[i] = INF;
        }
    }
    if(ok1){
        ll l[n],r[n];
        priority_queue<ii,vector<ii>,greater<ii> >pq;
        f(i,0,n){
            pq.push(ii(a[i],i));
            while(pq.top().F < a[i]){
                r[pq.top().S] = i-1;
                pq.pop();
            }
        }
        while(!pq.empty()){
            r[pq.top().S] = n-1;
            pq.pop();
        }
        for(ll i=n-1;i >= 0;i--){
            pq.push(ii(a[i],i));
            while(pq.top().F < a[i]){
                l[pq.top().S] = i+1;
                pq.pop();
            }
        }
        while(!pq.empty()){
            l[pq.top().S] = 0;
            pq.pop();
        }
        ll ans = 0;
        ll dp[n+1];
        dp[0] = 0;
        f(i,1,n+1){
            dp[i] = 0;
            if(b[i-1] == INF || !(l[b[i-1]-1] <= i-1 && i-1 <= r[b[i-1]-1])){
                continue;
            }
            dp[i] = query(1,n+1,1,b[i-1],1) + 1;
            update(1,n+1,b[i-1],b[i-1],1,dp[i]);
            ans = max(ans,dp[i]);
        }
        cout<<ans<<endl;
        return 0;
    }
    if(ok2){
        ll ans = 0;
        ll ok = 0;
        ll posa = 0;
        f(i,0,n){
            if(a[i] > b[0]){
                ans += posa * ok;
                ok = 0;
                posa = 0;
            }
            else{
                posa++;
                ok |= (a[i] == b[0]);
            }
        }
        ans += posa * ok;
        cout<<ans<<endl;
        return 0;
    }
    ll l[n],r[n];
    priority_queue<ii,vector<ii>,greater<ii> >pq;
    f(i,0,n){
        pq.push(ii(a[i],i));
        while(pq.top().F < a[i]){
            r[pq.top().S] = i-1;
            pq.pop();
        }
    }
    while(!pq.empty()){
        r[pq.top().S] = n-1;
        pq.pop();
    }
    for(ll i=n-1;i >= 0;i--){
        pq.push(ii(a[i],i));
        while(pq.top().F < a[i]){
            l[pq.top().S] = i+1;
            pq.pop();
        }
    }
    while(!pq.empty()){
        l[pq.top().S] = 0;
        pq.pop();
    }
    ll dp[n+1][n+1];
    f(i,0,n+1){
        f(j,0,n+1){
            if(i == 0 || j == 0){
                dp[i][j] = 0;
            }
            else{
                dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                if(a[i-1] == b[j-1] && (l[i-1] <= j-1 && j-1 <= r[i-1])){
                    dp[i][j] = max(dp[i][j],dp[i][j-1] + 1);
                }
            }
        }
    }
    cout<<dp[n][n]<<endl;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 7 ms 460 KB Output is correct
3 Correct 95 ms 11320 KB Output is correct
4 Correct 16 ms 1100 KB Output is correct
5 Correct 112 ms 10364 KB Output is correct
6 Correct 18 ms 1096 KB Output is correct
7 Correct 20 ms 1104 KB Output is correct
8 Correct 88 ms 6984 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 4 ms 588 KB Output is correct
4 Correct 7 ms 944 KB Output is correct
5 Correct 6 ms 972 KB Output is correct
6 Correct 7 ms 972 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 844 KB Output is correct
2 Correct 48 ms 4984 KB Output is correct
3 Correct 175 ms 11972 KB Output is correct
4 Correct 160 ms 11980 KB Output is correct
5 Correct 187 ms 13624 KB Output is correct
6 Correct 178 ms 13164 KB Output is correct
7 Correct 157 ms 13168 KB Output is correct
8 Correct 169 ms 12360 KB Output is correct
9 Correct 201 ms 12584 KB Output is correct
10 Correct 121 ms 13196 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 1 ms 460 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 4 ms 588 KB Output is correct
10 Correct 7 ms 944 KB Output is correct
11 Correct 6 ms 972 KB Output is correct
12 Correct 7 ms 972 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 1 ms 460 KB Output is correct
22 Correct 7 ms 4300 KB Output is correct
23 Correct 2 ms 332 KB Output is correct
24 Correct 158 ms 98264 KB Output is correct
25 Correct 142 ms 98272 KB Output is correct
26 Correct 139 ms 98248 KB Output is correct
27 Correct 137 ms 98268 KB Output is correct
28 Correct 140 ms 98568 KB Output is correct
29 Correct 138 ms 98656 KB Output is correct
30 Correct 138 ms 98676 KB Output is correct
31 Correct 140 ms 98500 KB Output is correct
32 Correct 142 ms 98620 KB Output is correct