Submission #675213

#	Time	Username	Problem	Language	Result	Execution time	Memory
675213		Cookie	Global Warming (CEOI18_glo)	C++14	48 / 100	145 ms	8196 KiB

glo

#include<bits/stdc++.h>
 
using namespace std;
#include<fstream>
 
#define ll long long
#define vt vector
#define pb push_back
#define fi first
#define se second
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
typedef unsigned long long ull;
#define pii pair<int, int>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
const ll mod=  1e9 + 7;
const int mxk = 1e3, sq = 750, mxn = 1e5;
const ll inf = -1e18;
int n, x;
int d[mxn + 1][4];
struct BIT{
    int bit[mxn * 3 + 1];
    void upd(int p, int v){
        while(p <= mxn * 3){
            bit[p] = max(bit[p], v);
            p += p & (-p);
        }
    }
    int get(int p){
        int ans = 0;
        while(p){
            ans = max(ans, bit[p]);
            p -= p & (-p);
        }
        return(ans);
    }
};
BIT bit[4];
vt<ll>b;
ll a[mxn + 1];
int find(ll x){
    return(lower_bound(b.begin(), b.end(), x) - b.begin() + 1);
}
 
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> x;
    for(int i = 1; i <= n; i++){
        cin >> a[i]; b.pb(a[i] + x); b.pb(a[i] - x); b.pb(a[i]);
    }
    int ans = 0;
    sort(b.begin(), b.end());
    for(int i = 1; i <= n;  i++){
        d[i][0] = bit[0].get(find(a[i]) - 1) + 1; d[i][1] = max(bit[1].get(find(a[i] + x) - 1), bit[0].get(find(a[i] + x) - 1)) + 1; 
        d[i][2] = max(bit[2].get(find(a[i] - x) - 1), bit[0].get(find(a[i] - x) - 1)) + 1; 
        d[i][3] = max({bit[2].get(find(a[i]) - 1), bit[1].get(find(a[i]) - 1), bit[3].get(find(a[i]) - 1)}) + 1;
        bit[0].upd(find(a[i]), d[i][0]); bit[1].upd(find(a[i] + x), d[i][1]); bit[2].upd(find(a[i] - x), d[i][2]);
        bit[3].upd(find(a[i]), d[i][3]);
        ans = max({ans, d[i][0], d[i][1], d[i][2], d[i][3]});
    }
    cout << ans;
    return(0);
}

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