Submission #920060

#	Time	Username	Problem	Language	Result	Execution time	Memory
920060		Sir_Ahmed_Imran	Global Warming (CEOI18_glo)	C++17	28 / 100	2107 ms	151508 KiB

glo

                              ///~~~LOTA~~~///
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long 
#define append push_back
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define N 200001
#define M 1000000001
int a[N];
int Q[N];
class ST{
public:
    map<int,int> seg;
    void update(int i,int x,int v=1,int s=0,int e=M){
        if(e-s==1){
            seg[v]=x;
            return;
        }
        int mid,rc,lc;
        mid=(s+e)/2;
        rc=2*v+1;
        lc=2*v;
        if(i<mid) update(i,x,lc,s,mid);
        else update(i,x,rc,mid,e);
        seg[v]=max(seg[lc],seg[rc]);
    }
    int get(int l,int r,int v=1,int s=0,int e=M){
        if(r<=s || e<=l || l>=r) return 0;
        if(l<=s && e<=r) return seg[v];
        int mid,rc,lc;
        mid=(s+e)/2;
        rc=2*v+1;
        lc=2*v;
        return max(get(l,r,lc,s,mid),get(l,r,rc,mid,e));
    }
};
void solve(){
    int n,m,o,p,q,r;
    cin>>n>>m;
    ST x,y;
    for(int i=o=1;i<=n;i++)
        cin>>a[i];
    for(int i=n;i>0;i--){
        Q[i]=y.get(a[i],a[i]+1);
        y.update(a[i],y.get(a[i]+1,M)+1);
    }
    for(int i=1;i<=n;i++){
        p=x.get(0,a[i])+1;
        y.update(a[i],Q[i]);
        x.update(a[i],p);
        o=max(o,p+y.get(max(a[i]-m+1,0),M));
    }
    cout<<o;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

Compilation message (stderr)

glo.cpp: In function 'void solve()':
glo.cpp:42:17: warning: unused variable 'q' [-Wunused-variable]
   42 |     int n,m,o,p,q,r;
      |                 ^
glo.cpp:42:19: warning: unused variable 'r' [-Wunused-variable]
   42 |     int n,m,o,p,q,r;
      |                   ^

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25