0w1

ABC 14 C - AtColor ( Imosu + Discretization )

C: AtColor - AtCoder Beginner Contest 014 | AtCoder
Problem Statement: Given n ranges [ a[ i ], b[ i ] ], find the maximum covered count of any point. We can use imosu algorithm, where we maintain the value of difference for two adjacent values, thus making it possible to update in O( 1 ) for adding an entire range. For example, if we will add the whole range [ 2, 7 ] by 1, we can add a[ 2 ] - a[ 1 ] by 1, and subtract a[ 8 ] - a[ 7 ] by 1. We will only make query in the end, where
{ \displaystyle
a_i = \sum_{j=1}^{i} a_j - a_{j-1}
}

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXAB = 1e6 + 6;

int n;
int a[ MAXN ], b[ MAXN ];

int seg[ MAXAB ];

void solve(){
    for(int i = 0; i < n; ++i){
        ++seg[ a[ i ] ];
        --seg[ b[ i ] + 1 ];
    }
    int max_cnt = 0;
    int cur_cnt = 0;
    for(int i = 0; i < MAXAB; ++i){
        cur_cnt += seg[ i ];
        if( cur_cnt > max_cnt ){
            max_cnt = cur_cnt;
        }
    }
    printf("%d\n", max_cnt);
}

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        scanf("%d%d", &a[ i ], &b[ i ]);
    solve();
    return 0;
}

Here's the discretized version though it is not required for this problem. It will reduce the time complexity from O( n + k ) to O( n ), though I used STL map to maintain the index and became O( n lg n ).

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXAB = 1e6 + 6;
 
int n;
int a[ MAXN ], b[ MAXN ];
 
int seg[ 2 * MAXN ];
map<int, int> pidx;
 
void discretize(){
    vector<int> seg;
    for(int i = 0; i < n; ++i){
        seg.push_back( a[ i ] );
        seg.push_back( b[ i ] + 1 );
    }
    sort( seg.begin(), seg.end() );
    seg.resize( unique( seg.begin(), seg.end() ) - seg.begin() );
    for(int i = 0; i < seg.size(); ++i)
        pidx[ seg[ i ] ] = i;
}
 
void solve(){
    discretize();
    for(int i = 0; i < n; ++i){
        ++seg[ pidx[ a[ i ] ] ];
        --seg[ pidx[ b[ i ] + 1 ] ];
    }
    int max_cnt = 0, cur_cnt = 0;
    for(int i = 0; i < MAXN; ++i){
        cur_cnt += seg[ i ];
        max_cnt = max<int>( max_cnt, cur_cnt );
    }
    printf("%d\n", max_cnt);
}
 
int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        scanf("%d%d", &a[ i ], &b[ i ]);
    solve();
    return 0;
}