Makaty's blog

By Makaty, history, 5 weeks ago, In English

Hello, since gym doesn't allow to see others solutions could someone help with this problem:

i have tried this solution but got WA

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Makaty (previous revision, new revision, compare).

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

instructions unclear: solution page not able to be viewed please send your code in a code block instead

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    hello, sorry for that :), here is my code:

    #include <bits/stdc++.h>
    #define ll long long
    #define ull unsigned long long
    #define ff first
    #define ss second
    #define all(a) a.begin(), a.end()
    #define iinf INT_MAX
    #define pi pair<int,int>
    #define endl '\n'
    #define ld long double
    #define linf LONG_LONG_MAX
    #include<ext/pb_ds/assoc_container.hpp>
    #include<ext/pb_ds/tree_policy.hpp>
    using namespace __gnu_pbds;
    using namespace std;
    template<class T>
    using ordered_set = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;
    /*
    // find_by_order, order_of_key
    */
    void fastio(){ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
    void file(){
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);
    #endif
    }
     
    #define int ll
    #define mod (int)(1e9+7)
    int n,k;
    int t[300007];
    int dp[300007];
    int best(int cur) {
        if(cur == n) return 0;
        int &ret = dp[cur];
        if(ret != -1) return ret;
        ret = 1 + best(cur+1);
        if(t[cur] != -1) {
            for(int i = cur+1; i<=t[cur]; i++) {
                ret = min(ret,best(i));
            }
     
        }
        return ret;
    }
    void solve1() {
     
     
     
    }
     
     
    void solve() {
        cin >> n >> k;
        memset(t, -1, sizeof(t));
        memset(dp, -1, sizeof(dp));
        for(int i = 0; i<k; i++) {
            int a,b; cin >> a >> b;
            t[a] = b;
        }
        cout << best(1) << endl;
     
     
     
    }
     
    signed main() {
     
        file();
        fastio();
        int t = 1;
        cin >> t;
        while(t--) solve();
     
    }
    
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      2 declarations of $$$t$$$? One as an array and another as an input integer? Looks more like Compile Error than WA to me...

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        yeah i see, but unfortunately it wasn't compile error, when i used t in main the compiler took the block scope one instead of the global var so it worked

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

You actually don't need DP to solve this problem.

Think of it like this, Bus Stops means that you have segments in the form $$$(li, ri)$$$. In these segments you don't need to walk.

This means that if consecutive segments (let's say $$$(li, ri)$$$ & $$$(lj, rj)$$$ assuming $$$ri<=lj$$$ and $$$rj>=ri$$$) are intersecting you don't need to walk in the segment $$$(li, rj)$$$ at all.

So now this problem becomes for the distance (1, n) how many places have no segments. That is the answer. For merging segments you can sort and merge, I think it's pretty well known.

code