Submission #949977

#	Time	Username	Problem	Language	Result	Execution time	Memory
949977		berr	Cloud Computing (CEOI18_clo)	C++17	0 / 100	1 ms	3420 KiB

clo

#include <bits/stdc++.h>
using namespace std;
 
int st[4*200000+37];
map<int, int> c, e;
 
void update(int v, int l, int r, int pos, int val){
    if (l==r){ st[v] = val; return;}
 
    int mid = (r+l) / 2;
 
    if (pos <= mid) update(v*2, l, mid, pos, val);
    else update(v*2+1, mid+1, r, pos, val);
 
    st[v] = max(st[v*2+1], st[v*2]);
}
 
int get(int v, int l, int r, int tl, int tr){
    if(r<l || tl > r || tr < l || tr<tl) return 0;
    if(l>=tl && r<= tr) return st[v];
    int mid = (r+l) / 2;
 
    return max(get(v*2, l, mid, tl, tr), get(v*2+1, mid+1, r, tl, tr));
}
 
 
int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
 
    int n, x; cin >> n >> x;
    
    vector<int> a(n);
    vector<int> b, d, rb, rd;
 
 
    for (auto &i: a) cin >> i;
 
    for (int i = 0; i < n; i++){
        b.push_back(a[i]); d.push_back(a[i]-x);
    }
 
    sort(b.begin(), b.end());
    sort(d.begin(), d.end());
    int cnt=0;
 
    for (int i = 0; i < b.size(); i++){
        if(c.count(b[i])==0) c[b[i]] = cnt, cnt++;
    }
 
    cnt=0;
 
    for(int i=0; i<n; i++){
        if(e.count(d[i])==0) e[d[i]] = cnt, cnt++;
    }
 
    vector<int> pr(n), sf(n);
    int ans=0;
 
    for(int i=n-1; i>=0; i--){
        sf[i] = max(0, get(1, 0, n+1, c[a[i]]+1, n+1)) +1;
        ans=max(ans, sf[i]);
        update(1, 0, n+1, c[a[i]], sf[i]);
    }
 
    memset(st, 0, sizeof(st)); 
 
    
    for(int i=0; i<n; i++){
    
        int s=-1;
        for(int l=20; l>=0; l--){
            int tmp=s+(1LL<<l);
            if(tmp<n &&d[tmp] < a[i]){
                s=tmp;
            }
        }
 
        if(s!=-1)
        ans=max(ans, max(0, get(1, 0, n+1, 0, e[d[s]]))+sf[i]);
        
        pr[i] = max(0, get(1, 0, n+1, 0, e[a[i]-x]-1)) +1;
 
        update(1, 0, n+1, e[a[i]-x], pr[i]);
    
    }
 
 
 
 
    cout<<ans;
}

Compilation message (stderr)

clo.cpp: In function 'int32_t main()':
clo.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int i = 0; i < b.size(); i++){
      |                     ~~^~~~~~~~~~

• Subtask 1: 0 / 18
• Subtask 2: 0 / 18
• Subtask 3: 0 / 18
• Subtask 4: 0 / 18
• Subtask 5: 0 / 18
• Subtask 6: 0 / 10