제출 #73883

#제출 시각아이디문제언어결과실행 시간메모리
73883haitunGlobal Warming (CEOI18_glo)C++14
58 / 100
2055 ms4604 KiB
    #include <bits/stdc++.h>
    //#include "functions.h"
    #define FOR(x,y) for(int x = 0; x < y; x++)
    #define ALLR(x) x.begin(),x.end()
    #define con continue
    #define ll long long
    #define LINF LLONG_MAX
    #define INF INT_MAX
    #define pii pair<int,int>
    #define vi vector <int>
    #define pb push_back
    #define F first
    #define S second
    #define len(x) x.length()
    #define sz(x) x.size()
    #define SEE(v)	for(auto x : v)	cout << x << " "; cout << endl;
    using namespace std;
     
    int n, b;
     
    int CeilIndex(vi v, int l, int r, int key){
    	
    	while(r - l > 1)
    	{
    		int m = l + (r - l) / 2;
    		if (v[m] >= key)	r = m;
    		else				l = m;
    	}
     
    	return r;
    }
     
    int RCeilIndex(vi v, int l, int r, int key){
    	
    	while(r - l > 1)
    	{
    		int m = l + (r - l) / 2;
    		if(v[m] <= key)	r = m;
    		else			l = m;
    	}
     
    	return r;
    }
     
    int LongestIncreasingSubsequenceLength(vi v,vi &front){
     
    	if(v.size() == 0)	return 0;
     
    	vi tail(v.size(), INF);
    	int length = 1;
    	
    	front[0] = 0;
    	tail[0] = v[0];
    	
    	for(int i = 1; i < v.size(); i++)
    	{
    		int pos = upper_bound(ALLR(tail), v[i] + b - 1) - tail.begin();
    		//FOR(j, v.size())	if(tail[j] != INF)	cout << tail[j] << " "; else	cout << "0 ";
    		//cout << "Pos: " << pos << endl;
    		//cout << endl;
    		front[i] = pos;
    		
    		if(v[i] < tail[0])					tail[0] = v[i];
    		else if(v[i] > tail[length - 1])	tail[length++] = v[i];
    		else								tail[lower_bound(tail.begin(), tail.begin() + length - 1, v[i]) - tail.begin()] = v[i];
    	}
     
    	return length;
    }
     
    int LongestDecreasingSubsequenceLength(vi v, vi &back){
    	
    	if (v.size() == 0)	return 0;
     
    	vi tail(v.size(), 0);
    	int length = 1;
    	
    	back[0] = 1;
    	tail[0] = v[0];
    	
    	for(int i = 1; i < v.size(); i++)
    	{
    	    int pos = RCeilIndex(tail, -1, length - 1, v[i]);
    	    
    		if(v[i] > tail[0])					tail[0] = v[i], back[i] = 0;
    		else if (v[i] < tail[length - 1])	tail[length++] = v[i], back[i] = length;
    		else								tail[pos] = v[i], back[i] = pos + 1;
    		
    		//if you are not the head, length = 0;
    		
    		//back[i] = length;
    	}
     
    	return length;
    }
     
    int main(){
    	
    	//freopen("test.txt", "r",stdin);
    	//int n, b;
    	cin >> n >> b;
    	
    	vi t(n), front(n), back(n);
    	FOR(j, n)   cin >> t[j];
    	
    	int ans = LongestIncreasingSubsequenceLength(t, front);
    	
    	if(b == 0)
    	{
    		cout << LongestIncreasingSubsequenceLength(t, front);
    		return 0;
    	}
     
    	reverse(ALLR(t));
    	LongestDecreasingSubsequenceLength(t, back);
    	reverse(ALLR(back));
    	//SEE(front);
    	//SEE(back);
    	for(int j = n - 1; j >= 0; j--)	ans = max(ans, front[j] + back[j]);
    	cout << ans;
    }

컴파일 시 표준 에러 (stderr) 메시지

glo.cpp: In function 'int LongestIncreasingSubsequenceLength(std::vector<int>, std::vector<int>&)':
glo.cpp:55:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int i = 1; i < v.size(); i++)
                     ~~^~~~~~~~~~
glo.cpp: In function 'int LongestDecreasingSubsequenceLength(std::vector<int>, std::vector<int>&)':
glo.cpp:81:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int i = 1; i < v.size(); i++)
                     ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...