답안 #1096711

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1096711	2024-10-05T03:18:08 Z	Wewoo	Global Warming (CEOI18_glo)	C++17	28 / 100	2000 ms	16072 KB

#include <bits/stdc++.h>
 
using namespace std;
 
const int N=(int) 2e5+9;
#define int long long
unordered_map <long long , long long > nen;
 
long long a[N],f[N],temp[N],f2[N];
long long st[4*N];
long long res,dp;
int n,x,idx,t;
 
void up(int id, int l, int r, int vt, int val) {
 
    if (l>vt || r<vt) return;
 
    if (l==r ) {
        st[id]=val;
        return;
    }
 
//    if (vt==2)
//    cout<<l<<" "<<r<<endl;
    int m=(l+r)/2;
 
    up(id*2,l,m,vt,val);
    up(id*2+1,m+1,r,vt,val);
 
    st[id]=max(st[id*2],st[id*2+1]);
 
}
 
long long get(int id, int l, int r, int u, int v) {
    if (l>v || r <u) return (int) -1e12;
 
    if (u<=l && r<=v) return st[id];
 
    int m=(l+r)/2;
 
    long long get1=get(id*2,l,m,u,v);
    long long get2=get(id*2+1,m+1,r,u,v);
 
//    if (u==2) {
//        cout<<l<<" "<<r<<endl;
//        cout<<get1<<" "<<get2<<endl;
//        cout<<endl;
//    }
 
    return max(get1,get2);
}
 
int small(int l, int r,long long x) {
    int vt=r;
 
    while (l<=r) {
        int m=(l+r)/2;
        if (temp[m]<=x) vt=m,r=m-1;
        else l=m+1;
    }
 
    return vt;
}
 
void solve() {
    res=idx;
    int pos=nen[a[n]];
    up(1,1,t,pos,f2[n]);
 
 
    for (int i=n-1; i>=1; i--) {
      for (int j=i+1; j<=n;j++)
        if (a[j]>a[i]-x) res=max(res,f[i]+f2[j]);
       }
 
    cout<<res;
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
   // freopen("daydep.inp","r",stdin);
    //freopen("daydep.out","w",stdout);
 
    cin>>n>>x;
 
    for (int i=1; i<=n; i++)
        cin>>a[i];
 
    for (int i=1; i<=n; i++) {
        temp[idx+1]=(int) 1e12;
        int pos=lower_bound(temp+1,temp+idx+1,a[i])-temp;
        temp[pos]=a[i];
        idx=max(idx,pos);
        f[i]=pos;
    }
 
    for (int i=1; i<=n; i++) temp[i]=0;
    idx=0;
 
    for (int i=n; i>=1; i--) {
        temp[idx+1]=(int) -1e12;
        int pos=small(1,idx+1,a[i]);
        temp[pos]=a[i];
        idx=max(idx,pos);
        f2[i]=pos;
    }
 
    for (int i=1; i<=n; i++)
        temp[i]=a[i];
 
    sort(temp+1,temp+1+n);
 
    for (int i=1; i<=n; i++) {
        if (temp[i]!=temp[i-1]) t++;
        nen[temp[i]]=t;
    }
 
    solve();
    return 0;
}

Subtask #1
5.0 / 5.0

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct
6	Correct	348 KB	Output is correct
7	Correct	348 KB	Output is correct
8	Correct	348 KB	Output is correct
9	Correct	348 KB	Output is correct
10	Correct	348 KB	Output is correct
11	Correct	348 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	1 ms	464 KB	Output is correct

Subtask #3
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	1 ms	464 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	2 ms	348 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Correct	1 ms	348 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct
26	Correct	1 ms	348 KB	Output is correct

Subtask #4
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	2072 ms	16072 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	2051 ms	4280 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	2017 ms	8288 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	1 ms	464 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	2 ms	348 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Correct	1 ms	348 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct
26	Correct	1 ms	348 KB	Output is correct
27	Execution timed out	2072 ms	16072 KB	Time limit exceeded
28	Halted	0 ms	0 KB	-

답안 #1096711

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 10.0 / 10.0

Subtask #3 13.0 / 13.0

Subtask #4 0 / 10.0

Subtask #5 0 / 20.0

Subtask #6 0 / 17.0

Subtask #7 0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
10.0 / 10.0

Subtask #3
13.0 / 13.0

Subtask #4
0 / 10.0

Subtask #5
0 / 20.0

Subtask #6
0 / 17.0

Subtask #7
0 / 25.0