Submission #1344976

#TimeUsernameProblemLanguageResultExecution timeMemory
1344976nguyenkhangninh99Arcade (NOI20_arcade)C++20
0 / 100
1 ms344 KiB

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int maxn = 5e5 + 5;
int bit[maxn];

void update(int p, int val){
    for(; p < maxn; p += p & -p) bit[p] = max(bit[p], val);
}
int get(int p){
    int res = 0;
    for(; p; p -= p & -p) res = max(res, bit[p]);
    return res;
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    /*a[i] - a[j] <= t[i] - t[j];
    VÀ
    a[j] - a[i] <= t[i] - t[j];
    
    =>
    -(a[j] - t[j]) <= -(a[i] - t[i]);
    VÀ
    a[j] + t[j] <= a[i] + t[i];*/
    int n, m; cin >> n >> m;

    vector<array<int, 2>> a(n + 1);
    for(int i = 1; i <= m; i++) cin >> a[i][0];
    for(int i = 1; i <= m; i++) cin >> a[i][1];

    vector<int> cmp;
    for(int i = 1; i <= n; i++) a[i] = {a[i][0] + a[i][1], -(a[i][1] - a[i][0])};

    for(int i = 1; i <= n; i++) cmp.push_back(-a[i][1]);
    sort(cmp.begin(), cmp.end());
    cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());

    sort(a.begin(), a.end());

    for(int i = 1; i <= m; i++){
        int pos = lower_bound(cmp.begin(), cmp.end(), -a[i][1]) - cmp.begin() + 1;
        update(pos, get(pos - 1) + 1);
    }
    cout << *max_element(bit + 1, bit + maxn + 1);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...