Submission #47318187

---

Source Code Expand

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

// typedef tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> pbds; // find_by_order, order_of_key

typedef tree<pair<long long , long long>, null_type, less_equal<pair<long long , long long>>, rb_tree_tag, tree_order_statistics_node_update> pbds1; // find_by_order, order_of_key
// typedef tree<pair<long long , long long>, null_type, greater<pair<long long , long long>>, rb_tree_tag, tree_order_statistics_node_update> pbds2; // find_by_order, order_of_key

#define ll long long
// #define ll 
// #define ll int
#define ld long double
#define int long long
#define inf 1000000000000000005
// #define inf 1000000005
#define mod 998244353
typedef pair<int, int> pii;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
#define pb push_back
#define ppb pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sz(x) (ll)x.size()
// #define ckmin(a,b) a = min(a,b)
// #define ckmax(a,b) a = max(a,b)
#define _BENZ_ ios_base::sync_with_stdio(false);cin.tie(NULL);
// const int N = 2e5 + 10;

template<class T> bool ckmin(T&a, T&b) { bool B = a > b; a = min(a,b); return B; }
template<class T> bool ckmax(T&a, T&b) { bool B = a < b; a = max(a,b); return B; }

// std::cout << std::fixed;
// std::cout << std::setprecision(12);
// floor(2.3)
// ceil(2.3)

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
}; // unordered_map<ll , ll , custom_hash> mp;

long long expo(long long a, long long b, long long mod1) {long long res = 1; while (b > 0) {if (b & 1ll)res = (res * a) % mod1; a = (a * a) % mod1; b = b >> 1ll;} return res;}

/*::::::::::::::::::::::::::::::::::::::::::::::::::::::: SOLUTION TO THE PROBLEM :::::::::::::::::::::::::::::::::::::::::::::::::*/

/*--------------------------------------------------------------------------------------------------------------------------------------------*/
/*
     ~By Editorial.
     ANALYSE THE SAMPLES.
     Kuch bold mein likha hai toh use dyan se do bar padho.
     Think of the edge case (n == 1 ?).
     Don't get stuck on a single approach for a long time.
     Also don't get stuck on a single problem for a long time :)
     target : want to be in top 100 of div2 contest( CODEFORCES ).
     Agar kabhi koi easy problem kafi tough lagne lage problem ko do bar padh aur samples ko analyse kar
*/

/*

*/
const int _N = 200001;



void Pre() {
}

/*
    Dp se bhi soch
    Dp se bhi soch
    Dp se bhi soch
*/

ll dx[] = {0 ,  0 , 1 , -1 ,  1 , 1 , -1 , -1};
ll dy[] = {1 , -1 , 0 ,  0 , -1 , 1 ,  1 , -1}; 

ll n , d , w;
vll _t;
vector<vll> adj;

class ST{
public:

    vll t , lazy;

    ST(ll _n) {
        t.assign(4ll * (_n) + 7ll , 0ll);
        lazy.assign(4ll * (_n) + 7ll , 0ll);
    }   

    void build(ll ind , ll l , ll r) {
        if(l == r) {
            t[ind] = _t[l];
            return;  
        }

        ll mid = (l + r) / 2ll;

        build(2ll * ind , l , mid);
        build((2ll * ind) + 1ll , mid + 1ll , r);
        
        t[ind] = max(t[2ll * ind] , t[(2ll * ind) + 1ll]);
    }

    void update(ll ind , ll l , ll r , ll lx , ll rx , ll val) {
        if(lazy[ind]) {
            t[ind] += lazy[ind];
            
            if(l != r) {
                lazy[2ll * ind] += lazy[ind];
                lazy[(2ll * ind) + 1ll] += lazy[ind];
            }

            lazy[ind] = 0;
        }

        if((l > rx) or (r < lx)) return; 

        if((l >= lx) and (r <= rx)) {
            t[ind] += val;
            lazy[2ll * ind] += val; lazy[(2ll * ind) + 1ll] += val;

            return;
        }

        ll mid = (l + r) / 2ll;

        update(2ll * ind , l , mid , lx , rx , val);
        update((2ll * ind) + 1ll , mid + 1ll , r , lx , rx , val);

        t[ind] = max(t[2ll * ind] , t[(2ll * ind) + 1ll]); 
    }

    ll get_max() {
        return t[1ll];
    }
};

void solve() {
    // cout << "HAR HAR MAHADEV" << "\n";
    cin >> n >> d >> w;

    ST _s(_N); adj.assign(_N + 7ll , {}); _t.assign(_N + 7ll , 0ll);

    for(ll i = 1; i <= n; ++i) {
        ll x , t; cin >> t >> x;
        adj[x].pb(t);
    }

    for(ll i = 1; i <= _N - 1ll; ++i) {
        sort(adj[i].begin() , adj[i].end());
    }

    for(ll i = 1; i <= min(_N - 1ll , w); ++i) {
        for(ll j = 0; j < sz(adj[i]); ++j) {
            _t[adj[i][j]]++;
        }
    }

    ll sum = 0ll;

    for(ll i = 1; i <= min(d , _N - 1ll); ++i) {
        sum += _t[i];
    }

    for(ll i = 1ll; i <= (_N - 1ll) - d + 1ll ; ++i) {
        ll _sum = sum;
        sum -= _t[i]; sum += _t[i + d];
        
        _t[i] = _sum;
        // ++_inx;
    } 

    _s.build(1ll , 1ll , _N - 1ll);

    ll ans = 0ll;

    ans = max(_s.get_max() , ans);

    for(ll i = 1ll; i <= (_N - 1ll) - w + 1ll ; ++i) {
        for(ll j = 0; j < sz(adj[i]); ++j) {
            _s.update(1ll , 1ll , _N - 1ll , max(adj[i][j] - d + 1ll , 1ll) , adj[i][j]  , -1);
        }

        for(ll j = 0; j < sz(adj[i + w]); ++j) {
           _s.update(1ll , 1ll , _N - 1ll , max(adj[i + w][j] - d + 1ll , 1ll) , adj[i + w][j] , 1);
        }

        ans = max(ans , _s.get_max());
    }

    cout << ans << "\n";
}    

int32_t main(){

    // freopen("teamwork.in","r",stdin);
    // freopen("teamwork.out","w",stdout);
    // //OR
    // ifstream fin("input.in");
    // ofstream fout("output.out");

    #ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

    freopen("output.txt", "w", stdout);

    #endif // ONLINE_JUDGE  

    _BENZ_

    Pre();

    ll t = 1;
    // cin >> t;

    while(t--){
        solve();
    }

    // for(ll i = 1; i <= t; ++i) {
    //       cout << "Case "<<i<<": ";
    //       solve();
    // }

    return 0;
}


/*

*/

Submission Info

Judge Result