Submission #547427

#	Time	Username	Problem	Language	Result	Execution time	Memory
547427		Danilo21	Global Warming (CEOI18_glo)	C++14	100 / 100	1421 ms	193488 KiB

glo

#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define en '\n'
#define sp ' '
#define tb '\t'
#define ri(n) int n; cin >> n
#define rl(n) ll n; cin >> n
#define rs(s) string s; cin >> s
#define rc(c) char c; cin >> c
#define rv(v) for (auto &x : v) cin >> x
#define pven(v) for (auto x : v) cout << x << en
#define pv(v) for (auto x : v) cout << x << sp; cout << en
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define yes cout << "YES" << en
#define no cout << "NO" << en
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define ssort(a, b) if (a < b) swap(a, b)
#define bitcnt(a) __builtin_popcountll(a)
#define bithigh(a) 63-__builtin_clzll(a)
#define lg bithigh
ll highpow(ll a) { return 1LL << (ll)lg(a); }

using namespace std;

struct node{
    int val;
    node* child[2];
    node(int v = 0){ val = v; child[0] = child[1] = nullptr; }
    node* ch(int i){ if (!child[i]) child[i] = new node(); return child[i]; }
};

class segtree{
private:
    ll n;
    node* root;

    void init(ll s){
        n = highpow(s);
        if (bitcnt(s) > 1) n <<= 1;
        root = new node();
    }

    int update(node* s, ll l, ll r, ll pos, int x){
        if (pos < l || pos > r) return s->val;
        if (l == r) return s->val = x;
        ll m = (l + r)>>1;
        int a = 0, b = 0;
        if (pos <= m){
            a = update(s->ch(0), l, m, pos, x);
            if (s->child[1]) b = s->child[1]->val;
        }
        else{
            b = update(s->ch(1), m+1, r, pos, x);
            if (s->child[0]) a = s->child[0]->val;
        }
        return s->val = max(a, b);
    }

    int query(node* s, ll l, ll r, ll ql, ll qr) const {
        if (ql > r || qr < l) return 0;
        if (l >= ql && r <= qr) return s->val;
        ll m = (l + r)>>1;
        int a = 0, b = 0;
        if (s->child[0]) a = query(s->ch(0), l, m, ql, qr);
        if (s->child[1]) b = query(s->ch(1), m+1, r, ql, qr);
        return max(a, b);
    }
public:
    segtree(ll n){ init(n); }
    void update(ll pos, int x){ update(root, 0, n-1, pos, x); }
    int query(ll l, ll r) const { if (l>r) return 0; return query(root, 0, n-1, l, r); }
};

const ll LINF = 4e18;
const int mxN = 2e5+10, INF = 2e9, mod = (1 ? 1e9+7 : 998244353);
ll n, m, a[mxN];
segtree* st[2];

void Solve(){

    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    map<ll, vector<array<int, 2> > > mp;
    st[0] = new segtree(INF);
    st[1] = new segtree(INF);
    for (int i = n-1; ~i; i--){
        int x = st[1]->query(a[i]+m+1, INF);
        if (x+1 > st[1]->query(a[i]+m, a[i]+m))
            st[1]->update(a[i]+m, x+1);
        mp[a[i]].pb({x+1, i});
    }
    for (auto& [k, v] : mp) sort(all(v));
    int ans = 0;
    for (int i = 0; i < n; i++){
        while (mp[a[i]].size() && mp[a[i]].back()[1] <= i) mp[a[i]].pop_back();
        int t = 0;
        if (mp[a[i]].size()) t = mp[a[i]].back()[0];
        st[1]->update(a[i]+m, t);
        int x = st[0]->query(0, a[i]-1);
        if (x+1 > st[0]->query(a[i], a[i]))
            st[0]->update(a[i], x+1);
        smax(ans, x+1 + st[1]->query(a[i]+1, INF));
    }
    cout << ans << en;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0); cerr.tie(0);
    cout << setprecision(12) << fixed;
    cerr << setprecision(12) << fixed;
    cerr << "Started!" << endl;

    int t = 1;
    //cin >> t;
    while (t--)
        Solve();

    return 0;
}

Compilation message (stderr)

glo.cpp: In function 'long long int highpow(long long int)':
glo.cpp:26:22: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   26 | #define bithigh(a) 63-__builtin_clzll(a)
      |                      ^
glo.cpp:27:12: note: in expansion of macro 'bithigh'
   27 | #define lg bithigh
      |            ^~~~~~~
glo.cpp:28:38: note: in expansion of macro 'lg'
   28 | ll highpow(ll a) { return 1LL << (ll)lg(a); }
      |                                      ^~
glo.cpp: In function 'void Solve()':
glo.cpp:100:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  100 |     for (auto& [k, v] : mp) sort(all(v));
      |                ^

• 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