Submission #73779

#	Time	Username	Problem	Language	Result	Execution time	Memory
73779		haitun	Global Warming (CEOI18_glo)	C++14	55 / 100	2051 ms	4624 KiB

glo

#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 debug cout << "\nPass line " + to_string(_LINE_) + "\n"
using namespace std;
void show(vi list){
	#ifdef debug
		FOR(j, sz(list))	cout << list[j] << " ";
		cout << endl;
	#endif
}
//#define debug cout << endl

int CeilIndex(std::vector<int> &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(std::vector<int> &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(vector<int> v,vi &front){
	
    if(v.size() == 0)	return 0;
 
    vector<int> tail(v.size(), 0);
    int length = 1; // always points empty slot in tail
	front[0] = 1;
    tail[0] = v[0];
    for(int i = 1; i < v.size(); i++)
	{
        if(v[i] < tail[0])
            // new smallest value
            tail[0] = v[i];
        else if (v[i] > tail[length - 1])
            // v[i] extends largest subsequence
            tail[length++] = v[i];
        else
            // v[i] will become end candidate of an existing subsequence or
            // Throw away larger elements in all LIS, to make room for upcoming grater elements than v[i]
            // (and also, v[i] would have already appeared in one of LIS, identify the location and replace it)
            tail[CeilIndex(tail, -1, length - 1, v[i])] = v[i];
        front[i] = length;
    }
    
    return length;
}

int LongestDecreasingSubsequenceLength(vector<int> v, vi &back) {
    if (v.size() == 0)	return 0;
    
    vector<int> tail(v.size(), 0);
    int length = 1; // always points empty slot in tail
	back[0] = 1;
    tail[0] = v[0];
    for(int i = 1; i < v.size(); i++)
	{
        if(v[i] > tail[0])					tail[0] = v[i];
        else if (v[i] < tail[length - 1])	tail[length++] = v[i];
        //here
        else								tail[RCeilIndex(tail, -1, length - 1, v[i])] = v[i];
        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;
    }
    
    
    else if(b == (int)pow(10,9)){
        reverse(ALLR(t));
    int cwbeiuvbwierb4ev = LongestDecreasingSubsequenceLength(t, back);
    reverse(ALLR(back));
	
    FOR(j, n)
    {
    	//cout << front[j] << " " << back[j] << endl;
    	ans = max(ans, front[j] + back[j + 1]);
	}
	cout << ans;
        return 0;
    }
	for(int k = -b; k <= b; k++)
    {
        if(k == 1 - b)   k = b;
        vi temp = t;
        FOR(i, n)
        {
            FOR(q,i)    temp[q] += k;
            ans = max(ans, LongestIncreasingSubsequenceLength(temp, front));
                
            temp = t;
                
            for(int q = n - 1; q > i; q--)  temp[q] += k;
            ans = max(ans, LongestIncreasingSubsequenceLength(temp, front));
        }
    }
    
    cout << ans;
}

Compilation message (stderr)

glo.cpp: In function 'void show(std::vector<int>)':
glo.cpp:3:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(x,y) for(int x = 0; x < y; x++)
                                   ^
glo.cpp:20:3: note: in expansion of macro 'FOR'
   FOR(j, sz(list)) cout << list[j] << " ";
   ^~~
glo.cpp: In function 'int LongestIncreasingSubsequenceLength(std::vector<int>, std::vector<int>&)':
glo.cpp:58:22: 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:84:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i < v.size(); i++)
                    ~~^~~~~~~~~~
glo.cpp: In function 'int main()':
glo.cpp:112:9: warning: unused variable 'cwbeiuvbwierb4ev' [-Wunused-variable]
     int cwbeiuvbwierb4ev = LongestDecreasingSubsequenceLength(t, back);
         ^~~~~~~~~~~~~~~~

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