### Makaty's blog

By Makaty, history, 4 weeks ago,

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

i have tried this solution but got WA

• 0

 » 4 weeks ago, # |   0 Auto comment: topic has been updated by Makaty (previous revision, new revision, compare).
 » 4 weeks ago, # |   0 instructions unclear: solution page not able to be viewed please send your code in a code block instead
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 hello, sorry for that :), here is my code: #include #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 #define endl '\n' #define ld long double #define linf LONG_LONG_MAX #include #include using namespace __gnu_pbds; using namespace std; template using ordered_set = tree,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> a >> b; t[a] = b; } cout << best(1) << endl; } signed main() { file(); fastio(); int t = 1; cin >> t; while(t--) solve(); } 
•  » » » 4 weeks ago, # ^ |   0 2 declarations of $t$? One as an array and another as an input integer? Looks more like Compile Error than WA to me...
•  » » » » 4 weeks ago, # ^ |   0 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
 » 4 weeks ago, # |   0 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. codevoid solve() { cin >> n >> k; vpii a(k); rep(i, k) cin >> a[i].fi >> a[i].se; sor(a); vpii b; rep(i, k) { if(b.empty() || b.bk.se < a[i].fi)b.pb(a[i]); else chkmax(b.bk.se, a[i].se); } debug(b) ll res = 0; if(b.empty()) { print(n-1); return; } res += b.ft.fi - 1; rep(i, sz(b)-1) { res += b[i+1].fi-b[i].se; } res += n - b.bk.se; print(res); } 
•  » » 4 weeks ago, # ^ |   +2 thx, appreciate that!