제출 #1178276

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1178276		zyadhany	Global Warming (CEOI18_glo)	C++20	100 / 100	741 ms	108168 KiB

glo

#include <bits/stdc++.h>
#include <chrono>
#include <random>
#include <unordered_map>
#include <unordered_set>
 
#define ll long long
#define vi vector<ll>
#define vii vector<vi>
#define pl pair<ll, ll>
#define all(X) X.begin(),X.end()
#define vp vector<pl>
#define mi map<ll,ll>
 
#define ld long double
#define vc vector<char>
#define vcc vector<vc>
#define mc map<char,int>
#define sortx(X) sort(X.begin(),X.end());
#define allr(X) X.rbegin(),X.rend()
#define ln '\n'
#define YES {cout << "YES\n"; return;}
#define NO {cout << "NO\n"; return;}
#define MUN {cout << "-1\n"; return;}
using namespace std;

const int MODE = 998244353;


/**
 * usage:-
 * creat tree element.
 * SegmentTree sg;
 * 
 * Functions you can use:
 * @set: set index or range to value.
 * @geteange: get value of given range.
 * @build: build tree with given vector or size.
 * 
 * make sure to look at item typedef.
 * you can change merge function to change it's oppration.
 * it you want to make change to segment work in checkLazy().
*/

typedef long long item;
/*
struct item
{
    int val;

    item(){
        val = 0;
    }
};
*/

class SegmentTree
{
public:

    void set(int index, int value) {
        set(0, 0, size - 1, index, value);
    }
    item getrange(int l, int r) {
        return (getrange(0, 0, size - 1, l, r));
    }

    void build(int n) {
        size = 1;
        while (size < n)
            size *= 2;
        tree.assign(size * 2, item());
        lazy.assign(size * 2, 0);
    }
private:
    int size;
    vector<item> tree;
    vector<long long> lazy;

    item merge(item a, item b) {
        item res = max(a, b);
        return (res);
    }

    void set(int m, int lx, int rx, int pos, ll val) {
        if (pos < lx || rx < pos) return;
        if (lx == rx && lx == pos)
        {
            tree[m] = val;
            return;
        }

        int mid = (lx + rx) / 2;
        item s1, s2;

        set(m * 2 + 1, lx, mid, pos, val);
        set(m * 2 + 2, mid + 1, rx, pos, val);
        s1 = tree[m * 2 + 1], s2 = tree[m * 2 + 2];

        tree[m] = merge(s1, s2);
    }

    item getrange(int m, int lx, int rx, int l, int r) {
        if (rx < l || r < lx) return (0);
        if (l <= lx && rx <= r) return (tree[m]);

        int mid = (lx + rx) / 2;
        item s1, s2;

        s1 = getrange(m * 2 + 1, lx, mid, l, r);
        s2 = getrange(m * 2 + 2, mid + 1, rx, l, r);

        return merge(s1, s2);
    }
};


void solve(ll tc) {
    ll n, m;

    cin >> n >> m;

    vi X(n);
    set<ll> stc;
    for (int i = 0; i < n; i++) {
        cin >> X[i];
        stc.insert({X[i], X[i] + m});
    }

    mi CO;
    for (auto a : stc) CO[a] = CO.size();

    SegmentTree sgsuff;
    sgsuff.build(CO.size());

    vii suffval(CO.size(), vi(2, 0));
    vi suff(n + 1);
    for (int i = n - 1; i >= 0; i--)
    {
        ll a = CO[X[i]+m];
        suff[i] = sgsuff.getrange(a+1, CO.size()-1) + 1;
        sgsuff.set(a, suff[i]);
        suffval[a].push_back(suff[i]);
    }
    

    ll sol = *max_element(all(suff));
    SegmentTree sgpref;
    sgpref.build(CO.size());
    for (int i = 0; i < n-1; i++)
    {
        ll a = CO[X[i]];
        ll b = CO[X[i]+m];
        suffval[b].pop_back();
        sgsuff.set(b, suffval[b].back());
    
        ll re = sgpref.getrange(0, a-1)+1;
        sgpref.set(a, re);
        ll v = sgsuff.getrange(a+1, CO.size()-1);
        sol = max(sol, re + v );
    }
    
    cout << sol << '\n';
}
 
int32_t main()
{
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int size = 1;   

    // freopen("disrupt.in", "r", stdin   );
    // freopen("disrupt.out", "w", stdout);
    // cin >> size;
    for (int tc = 1; tc <= size; tc++){
        solve(tc);
       // if (tc != size) cout << '\n';
    }
}

• 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