답안 #1007789

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1007789	2024-06-25T13:25:59 Z	andecaandeci	Global Warming (CEOI18_glo)	C++17	62 / 100	37 ms	7900 KB

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i=a; i<=(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b); i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a,x) for (auto& a : x)
#define int long long
#define ld long double
#define lb lower_bound
#define ceil(a,b) (a+(b-1))/b
#define ins insert
#define ub upper_bound
#define pb push_back
#define VI vector<int> 
#define VVI vector<VI> 
#define PII pair<int,int> 
#define VII vector<PII> 
#define size(x) x.size()
#define all(x) x.begin(), x.end()
#define fi first
#define se second
// const int mod = 1e9+7;
// const int N = 2e5 + 5;
// const int mod = 998244353;

int binser(vector<int>&temp,int num){
    int l =0,r=size(temp)-1,ind=0,mid;
    while(l<=r){
        mid=(l+r)/2;
        if(num>=temp[mid]){
            ind=mid;
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    // if(num>=temp[ind]){
        return ind;

    // }
    // else return -1;
}
int binserans(vector<int>&temp,int num){
    int l =0,r=size(temp)-1,ind=-1,mid;
    while(l<=r){
        mid=(l+r)/2;
        if(num<=temp[mid]){
            ind=mid;
            l=mid+1;
        }
        else{
            r=mid-1;
        }
    }
    // if(num>=temp[ind]){
        return ind+1;

    // }
    // else return -1;
}
void solve(){
    int n,k;
    cin>>n>>k;
    int arr[n];
    for(int i =0 ;i<n;i++){
        cin>>arr[i];
    }
    int inc[n],linc[n];
    inc[0]=arr[0];
    linc[0]=1;
    vector<int> temp;
    int ans=0;
    temp.push_back(arr[0]);
    for (int i = 1; i < n; i++) {
        if (arr[i] > temp.back()) {
            temp.push_back(arr[i]);
        } else {
            int ind = lower_bound(temp.begin(), temp.end(), arr[i]) - temp.begin();
            temp[ind] = arr[i];
        }
        inc[i]=temp.back();
        linc[i]=size(temp);
    }
    
    ans=size(temp);
    temp.clear();
    temp.push_back(arr[n-1]);
    for (int i = n-2; i >= 0; i--) {
        // trav(it,temp){
        //     cout<<it<<" ";
        // }
        // cout<<endl;
        // dbg(linc[i],inc[i],temp,inc[i]-k+1,binserans(temp,inc[i]-k+1));
        ans=max(ans,(int)(linc[i]+binserans(temp,inc[i]-k+1)));

        if (arr[i] < temp.back()) {
            temp.push_back(arr[i]);
        } else {
            int ind=binser(temp,arr[i]);
            temp[ind] = arr[i];
        }
        

    }



    cout<<ans<<endl;


}


int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    cout<<setprecision(12)<<fixed;
    // cin>>t; 
    while(t--){
        
        solve();
    }
}

Subtask #1
5.0 / 5.0

#	결과	메모리	Grader output
1	Correct	344 KB	Output is correct
2	Correct	344 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	344 KB	Output is correct
11	Correct	348 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	메모리	Grader output
1	Correct	344 KB	Output is correct
2	Correct	344 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	344 KB	Output is correct
11	Correct	348 KB	Output is correct
12	Correct	348 KB	Output is correct
13	Correct	348 KB	Output is correct
14	Correct	348 KB	Output is correct
15	Correct	348 KB	Output is correct
16	Correct	348 KB	Output is correct
17	Correct	348 KB	Output is correct
18	Correct	344 KB	Output is correct

Subtask #3
0 / 13.0

#	결과	메모리	Grader output
1	Correct	344 KB	Output is correct
2	Correct	344 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	344 KB	Output is correct
11	Correct	348 KB	Output is correct
12	Correct	348 KB	Output is correct
13	Correct	348 KB	Output is correct
14	Correct	348 KB	Output is correct
15	Correct	348 KB	Output is correct
16	Correct	348 KB	Output is correct
17	Correct	348 KB	Output is correct
18	Correct	344 KB	Output is correct
19	Correct	348 KB	Output is correct
20	Incorrect	348 KB	Output isn't correct
21	Halted	0 KB	-

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	6864 KB	Output is correct
2	Correct	34 ms	6992 KB	Output is correct
3	Correct	35 ms	6868 KB	Output is correct
4	Correct	34 ms	7000 KB	Output is correct
5	Correct	32 ms	7244 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	1884 KB	Output is correct
2	Correct	8 ms	1880 KB	Output is correct
3	Correct	8 ms	1884 KB	Output is correct
4	Correct	4 ms	2140 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	4 ms	2140 KB	Output is correct
7	Correct	7 ms	1884 KB	Output is correct

Subtask #6
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	3772 KB	Output is correct
2	Correct	25 ms	3524 KB	Output is correct
3	Correct	33 ms	7004 KB	Output is correct
4	Correct	32 ms	7380 KB	Output is correct
5	Correct	16 ms	3788 KB	Output is correct
6	Correct	14 ms	7128 KB	Output is correct
7	Correct	18 ms	7900 KB	Output is correct
8	Correct	13 ms	3796 KB	Output is correct

Subtask #7
0 / 25.0

#	결과	메모리	Grader output
1	Correct	344 KB	Output is correct
2	Correct	344 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	344 KB	Output is correct
11	Correct	348 KB	Output is correct
12	Correct	348 KB	Output is correct
13	Correct	348 KB	Output is correct
14	Correct	348 KB	Output is correct
15	Correct	348 KB	Output is correct
16	Correct	348 KB	Output is correct
17	Correct	348 KB	Output is correct
18	Correct	344 KB	Output is correct
19	Correct	348 KB	Output is correct
20	Incorrect	348 KB	Output isn't correct
21	Halted	0 KB	-

답안 #1007789

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 10.0 / 10.0

Subtask #3 0 / 13.0

Subtask #4 10.0 / 10.0

Subtask #5 20.0 / 20.0

Subtask #6 17.0 / 17.0

Subtask #7 0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
10.0 / 10.0

Subtask #3
0 / 13.0

Subtask #4
10.0 / 10.0

Subtask #5
20.0 / 20.0

Subtask #6
17.0 / 17.0

Subtask #7
0 / 25.0