Submission #1095033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095033		SoMotThanhXuan	Global Warming (CEOI18_glo)	C++17	100 / 100	241 ms	8528 KiB

glo

#include <bits/stdc++.h>
using namespace std;
const int maxN = 2e5 + 5;
int N, X, T[maxN];
namespace subtask1{
    bool check(){
        return X <= 50 && N <= 50;
    }
    int b[55], f[55];
    int res = 0;
    void sol(int a[]){
        for(int i = 1; i <= N; ++i)f[i] = 0;
        int ans = 0;
        for(int i = 1; i <= N; ++i){
            f[i] = 1;
            for(int j = 1; j < i; ++j){
                if(b[j] < b[i]) f[i] = max(f[i], f[j] + 1);
            }
            ans = max(ans, f[i]);
        }
        res = max(res, ans);
    }
    void solve(){
        for(int d = -X; d <= X; ++d){
            for(int i = 1; i <= N; ++i){
                for(int j = i; j <= N; ++j){
                    for(int k = 1; k <= N; ++k)b[k] = T[k];
                    for(int x = i; x <= j; ++x)b[x] += d;
                    sol(b);
                }
            }
        }
        cout << res;
    }
}
namespace subtask3{
    int it[4 * maxN];
    int comp[maxN];
    bool check(){
        return X == 0;
    }
    void update(int id, int l, int r, int p, int v){
        if(l > p || r < p) return ;
        if(l == r){
            it[id] = v;
            return ;
        }
        int mid = l + r >> 1;
        if(p <= mid) update(id << 1, l, mid, p, v);
        else update(id << 1 | 1, mid + 1, r, p, v);
        it[id] = max(it[id << 1], it[id << 1 | 1]);
    }
    int get(int id, int l, int r, int u, int v){
        if(l > v || r < u) return 0;
        if(l >= u && r <= v) return it[id];
        int mid = l + r >> 1;
        return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
    }
    void solve(){
        for(int i = 1; i <= N; ++i)comp[i] = T[i];
        sort(comp + 1, comp + 1 + N);
        for(int i = 1; i <= N; ++i){
            T[i] = lower_bound(comp + 1, comp + 1 + N, T[i]) - comp;
            update(1, 1, N, T[i], get(1, 1, N, 1, T[i] - 1) + 1);
        }
        cout << it[1];
    }
}
namespace subtask6{
    int it[4 * maxN];
    void build(int id, int l, int r){
        if(l == r){
            it[id] = 0;
            return ;
        }
        int mid = l + r >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
        it[id] = 0;
    }
    void update(int id, int l, int r, int p, int v){
        if(l > p || r < p) return ;
        if(l == r){
            it[id] = v;
            return ;
        }
        int mid = l + r >> 1;
        if(p <= mid) update(id << 1, l, mid, p, v);
        else update(id << 1 | 1, mid + 1, r, p, v);
        it[id] = max(it[id << 1], it[id << 1 | 1]);
    }
    int get(int id, int l, int r, int u, int v){
        if(l > v || r < u) return 0;
        if(l >= u && r <= v) return it[id];
        int mid = l + r >> 1;
        return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
    }
    int comp[maxN];
    #define left __left
    #define right __right
    int left[maxN], right[maxN];
    int tmp[maxN];
    void solve(){
        for(int i = 1; i <= N; ++i)comp[i] = T[i];
        sort(comp + 1, comp + 1 + N);
        for(int i = 1; i <= N; ++i)tmp[i] = lower_bound(comp + 1, comp + 1 + N, T[i]) - comp;
        for(int i = 1; i <= N; ++i){
            left[i] = get(1, 1, N, 1, tmp[i] - 1) + 1;
            update(1, 1, N, tmp[i], left[i]);
        }
        build(1, 1, N);
        for(int i = N; i >= 1; --i){
            right[i] = get(1, 1, N, tmp[i] + 1, N) + 1;
            update(1, 1, N, tmp[i], right[i]);
        }
        int res = it[1];
        build(1, 1, N);
        for(int i = 1; i <= N; ++i){
            int x = lower_bound(comp + 1, comp + 1 + N, T[i] + X) - comp;
            res = max(res, get(1, 1, N, 1, x - 1) + right[i]);
            update(1, 1, N, tmp[i], left[i]);
        }
        cout << res;
    }
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> N >> X;
    for(int i = 1; i <= N; ++i)cin >> T[i];
//    if(subtask1 :: check()) return subtask1 :: solve(), 0;
//    if(subtask2 :: check()) return subtask2 :: solve(), 0;
//    if(subtask3 :: check()) return subtask3 :: solve(), 0;
//    if(subtask4 :: check()) return subtask4 :: solve(), 0;
//    if(subtask5 :: check()) return subtask5 :: solve(), 0;
    return subtask6 :: solve(), 0;
    return 0;
}
/*
8 0
7 3 5 12 2 7 3 4
*/

Compilation message (stderr)

glo.cpp: In function 'void subtask3::update(int, int, int, int, int)':
glo.cpp:48:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |         int mid = l + r >> 1;
      |                   ~~^~~
glo.cpp: In function 'int subtask3::get(int, int, int, int, int)':
glo.cpp:56:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |         int mid = l + r >> 1;
      |                   ~~^~~
glo.cpp: In function 'void subtask6::build(int, int, int)':
glo.cpp:76:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |         int mid = l + r >> 1;
      |                   ~~^~~
glo.cpp: In function 'void subtask6::update(int, int, int, int, int)':
glo.cpp:87:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |         int mid = l + r >> 1;
      |                   ~~^~~
glo.cpp: In function 'int subtask6::get(int, int, int, int, int)':
glo.cpp:95:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   95 |         int mid = l + r >> 1;
      |                   ~~^~~

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