CSES — Hotel Queries

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;
}

Комментарии (5)

Показать архивные | Написать комментарий?

kartik8800

4 года назад, # |

Give this a try : https://codeforces.com/blog/entry/77128

→ Ответить

dorijanlendvaj

Try using ios_base::sync_with_stdio(0); cin.tie(0);

Everule

You can traverse the segment tree itself, and go left as long as there is value greater than $$$r$$$ on the left node. You can see my solution here. https://cses.fi/problemset/result/545774/

The size is rounded up to the next power of $$$2$$$ to make a clean segment tree allowing for an easier implementation.

hello_hell

4 года назад, # ^ |

The link doesn't show anything to me. I think after solving this question, I will be able to see other's solutions. Would you please use idone or something like that.

Code

#include <iostream>
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
using ll = long long int;
template<typename T>
struct segment_tree{
    vector<T> segtree;
    int n;
    T (*join)(T,T);
    T base;
    segment_tree(vector<T> &a, T (*merge)(T,T), T defvalue){
        n=a.size();
        join=merge;
        base=defvalue;
        segtree.resize(2*n);
        for(int i=0;i<n;i++){
            segtree[n+i]=a[i];
        }
        for(int i=n-1;i>=1;i--){
            segtree[i]=join(segtree[2*i], segtree[2*i + 1]);
        }
    }
    void update(int pos, T val){
        segtree[pos]=val;
        pos>>=1;
        while(pos){
            segtree[pos]=join(segtree[2*pos],segtree[2*pos+1]);
            pos>>=1;
        }
    }
    T query(T val){
        if(segtree[1] < val){
            return 0;
        }
        int idx = 1;
        while(idx < n){
            if(segtree[2*idx] < val){
                idx = 2*idx + 1;
            }
            else{
                idx = 2*idx;
            }
        }
        update(idx, segtree[idx] - val);
        return idx - n + 1;
    }
    void debug(){
        for(int i=1;i<2*n;i++){
            cout<<segtree[i]<<" ";
        }
        cout<<"\n";
    }
};
int mx(int x, int y){
    return x > y ? x : y;
}
void solve(){
    int n,m;
    cin>>n>>m;
    vector<int> hotels(1<<(64 - __builtin_clz(n)));
    for(int i=0;i<n;i++){
        cin>>hotels[i];
    }
    segment_tree<int> segtree(hotels, mx, -1e9);
    for(int i=0;i<m;i++){
        int group;
        cin>>group;
        cout<<segtree.query(group)<<" ";
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

№	Пользователь	Рейтинг
1	tourist	3843
2	jiangly	3705
3	Benq	3628
4	orzdevinwang	3571
5	Geothermal	3569
5	cnnfls_csy	3569
7	jqdai0815	3530
8	ecnerwala	3499
9	gyh20	3447
10	Rebelz	3409

№	Пользователь	Вклад
1	maomao90	171
2	awoo	163
3	adamant	162
4	TheScrasse	157
5	nor	153
6	maroonrk	152
6	-is-this-fft-	152
8	Petr	146
9	orz	145
10	pajenegod	144

Блог пользователя hello_hell