| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 920060 | Sir_Ahmed_Imran | Global Warming (CEOI18_glo) | C++17 | 2107 ms | 151508 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
///~~~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)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
