Blog entries - Codeforces

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

Problem Statement : Hotel Queries

for this problem, I implemented two solutions. The first solution by using merge sort tree with simple vector and Second is by using merge sort tree with multiset. Both of the solutions are giving me TLE for 3 test cases. Could you please share a better approach.

First Solution

#include <iostream>
#include <algorithm> 
#include <string> 
//  #include <sstream> 
//  #include <fstream>
//  #include <iomanip> 
#include <chrono> 
#include <numeric>
#include <utility>
#include <functional>
 
#include <bitset>
#include <tuple>
#include <queue>
#include <stack>
#include <vector>
#include <array>
//  #include <unordered_map>
//  #include <unordered_set>
#include <set>
#include <map>
//  #include <deque>
 
#include <climits>
#include <cstring>
#include <cmath>
#include <cassert>
#include <cstdio>
using namespace std;
using namespace std::chrono;
//  using namespace placeholders;
//  using namespace __gnu_pbds;
//  template<typename TypeInfo>
//  using new_set = tree< // find_by_order & order_of_key
//                   TypeInfo ,
//                   null_type ,
//                   less<TypeInfo> ,
//                   rb_tree_tag ,
//                   tree_order_statistics_node_update 
//       > ;
 
void debug_out() { cerr << endl; }
 
template <typename HEAD, typename... TAIL>
void debug_out(HEAD H, TAIL... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef HELL_JUDGE
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 0
#endif
 
 
const int MAXM = (int)1e5+100;
const int MAXN = (int)2e5+100;
const int MOD = (int)1e9+7;
 
 
// default size is considered MAXN
long long arr[MAXN];
vector<int> seg_tree[4*MAXN];
 
 
// BUILD THE SEGMENT TREE 
void build(int current_node , int left_, int right_){
    if(left_ == right_) {
        seg_tree[current_node].push_back(arr[left_]);
        return ;
    }
    int mid_point = left_ + (right_ - left_) / 2;
    build(2*current_node, left_ , mid_point);
    build(2*current_node+1, mid_point+1 , right_);
    merge(
            seg_tree[current_node*2].begin() , seg_tree[2*current_node].end() , 
            seg_tree[current_node*2+1].begin() , seg_tree[2*current_node+1].end(), 
            back_inserter(seg_tree[current_node])
         );
    return ;
}
 
int query(int current_node , int start , int end , int member){
    if(seg_tree[current_node].back() < member){
        return -1;
    }
    if(start == end){
        if(seg_tree[current_node].back() < member){
            return -1;
        }else{
            seg_tree[current_node].back() -= member;
            return start;
        }
    }
    int mid = (start + end) /2;
    int ans=-1;
    if(seg_tree[2*current_node].back() >=member){
        ans = query(2*current_node , start , mid , member);
    }else{
        ans = query(2*current_node+1 ,mid+1 , end , member);
    }
    seg_tree[current_node].clear();
    merge(
            seg_tree[current_node*2].begin() , seg_tree[2*current_node].end() , 
            seg_tree[current_node*2+1].begin() , seg_tree[2*current_node+1].end(), 
            back_inserter(seg_tree[current_node])
         );
    return ans;
}
 
 
int main(void){
#ifdef HELL_JUDGE
    freopen("input","r",stdin);
    freopen("output","w",stdout);
    freopen("error","w",stderr);
#endif 
#ifdef HELL_JUDGE
    auto INITIAL_TIME = high_resolution_clock::now();
#endif 
 
    int n , m; cin >> n >> m; 
    for(int i=0;i<n;++i){
        cin >> arr[i];
    }
    build(1 , 0 , n-1 );
    while(m--){
        int x; cin >> x; 
        cout << query(1 , 0 , n-1 , x) +1 << '\n'; 
    }
 
#ifdef HELL_JUDGE
    auto FINAL_TIME = high_resolution_clock::now();
    cout << "Time : "
        << duration_cast<milliseconds>(FINAL_TIME-INITIAL_TIME).count() 
        << " ms" << '\n'; 
#endif 
    return 0;
}

Second Solution

#include <iostream>
#include <algorithm> 
#include <string> 
//  #include <sstream> 
//  #include <fstream>
//  #include <iomanip> 
#include <chrono> 
#include <numeric>
#include <utility>
#include <functional>
 
#include <bitset>
#include <tuple>
#include <queue>
#include <stack>
#include <vector>
#include <array>
//  #include <unordered_map>
//  #include <unordered_set>
#include <set>
#include <map>
//  #include <deque>
 
#include <climits>
#include <cstring>
#include <cmath>
#include <cassert>
#include <cstdio>
using namespace std;
using namespace std::chrono;
//  using namespace placeholders;
using namespace __gnu_pbds;
template<typename TypeInfo>
using new_set = tree< // find_by_order & order_of_key
        TypeInfo ,
         null_type ,
         greater<TypeInfo> ,
         rb_tree_tag ,
         tree_order_statistics_node_update 
     > ;
 
void debug_out() { cerr << endl; }
 
template <typename HEAD, typename... TAIL>
void debug_out(HEAD H, TAIL... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef HELL_JUDGE
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 0
#endif
 
 
const int MAXM = (int)1e5+100;
const int MAXN = (int)2e5+100;
const int MOD = (int)1e9+7;
 
multiset<int , greater<int>> seg[4*MAXN];
long long arr[MAXN];
void build(int current_node , int start , int end){
    if(start == end){
        seg[current_node].insert(arr[start]);
        return; 
    }
    for(int i=start;i<=end; ++i){
        seg[current_node].insert(arr[i]);
    }
    int mid = (start + end) /2;
    build(2*current_node , start , mid);
    build(2*current_node +1 , mid+1 , end);
}
 
pair<int,int> query(int current  , int start , int end , int member){
    int x = *(seg[current].begin());
    if(x < member){
        return {-1,-1};
    }
    if(start==end){
        pair<int,int>p;
        p.first = x;
        p.second = start;
        seg[current].erase(seg[current].begin());
        if(x-member >0){
            seg[current].insert(x-member);
        }
        return p;
    }
    int mid = (start + end) /2;
    pair<int, int > ans;
    int y = *(seg[2*current].begin());
    if(y >= member){
        ans = query(2*current , start , mid , member);
    }else{
        ans = query(2*current+1 , mid+1 , end , member);
    }
    if(ans.first!=-1 && ans.second!=-1){
        auto itr = seg[current].find(ans.first);
        seg[current].erase(itr);
        if(ans.first - member >=0){
            seg[current].insert(ans.first-member);
        }
    }
    return ans;
}
 
int main(void){
#ifdef HELL_JUDGE
    freopen("input","r",stdin);
    freopen("output","w",stdout);
    freopen("error","w",stderr);
#endif 
#ifdef HELL_JUDGE
    auto INITIAL_TIME = high_resolution_clock::now();
#endif 
 
    int n , m; cin >> n >> m; 
    for(int i=0; i < n; ++i){
        cin >> arr[i];
    }
    build(1 , 0, n-1);
    while(m--){
        int x; cin >> x;
        pair<int,int> a = query(1 , 0 , n-1 , x) ;
        cout << a.second + 1 << '\n';
    }
 
#ifdef HELL_JUDGE
    auto FINAL_TIME = high_resolution_clock::now();
    cout << "Time : "
        << duration_cast<milliseconds>(FINAL_TIME-INITIAL_TIME).count() 
        << " ms" << '\n'; 
#endif 
    return 0;
}

Full text and comments »

hello_hell's blog