# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
880480 | 2023-11-29T13:50:11 Z | mkolko | Railway Trip 2 (JOI22_ho_t4) | C++14 | 2000 ms | 25432 KB |
#include <iostream> using namespace std; const int base=(1<<21); int tree[base*2+7]; int dp[base][30][2]; int main() { ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0); int n, m, k, q, p, p2, str, odp; cin>>n>>k; for(int a=0; a<=21; a++) { for(int i=0; i<=n; i++){ dp[i][a][0]=i; dp[i][a][1]=i; } } cin>>m; for(int a=0; a<m; a++) { cin>>p>>p2; if(p<=p2){ for(int i=0; i<p2-p+1 && i<k; i++) dp[p+i][0][1]=max(dp[p+i][0][1], p2); } else{ for(int i=0; i<p-p2+1 && i<k; i++) dp[p-i][0][0]=min(dp[p-i][0][0], p2); } } for(int a=1; a<=20; a++) { for(int i=1; i<=n; i++) { for(int q=dp[i][a-1][0]; q<=dp[i][a-1][1]; q++){ dp[i][a][1]=max(dp[i][a][1], dp[q][a-1][1]); dp[i][a][0]=min(dp[i][a][0], dp[q][a-1][0]); } } } /*for(int a=0; a<=n; a++) { for(int i=0; i<=n; i++) cout<<dp[a][i][1]<<" "; cout<<"\n"; } cout<<"\n\n"; for(int a=0; a<=n; a++) { for(int i=0; i<=n; i++) cout<<dp[a][i][0]<<" "; cout<<"\n"; }*/ cin>>q; for(int a=0; a<q; a++) { cin>>p>>p2; if(p<p2) { odp=0; for(int i=20; i>=0; i--){ if(dp[p][i][1]<p2){ odp=odp+(1<<(i)); p=dp[p][i][1]; } } } else { odp=0; for(int i=20; i>=0; i--){ if(dp[p][i][0]>p2){ odp=odp+(1<<(i)); p=dp[p][i][0]; } } } if(p!=p2) odp++; if(odp>=(1<<21)) cout<<-1<<"\n"; else cout<<odp<<" "<<"\n"; } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 348 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 348 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2027 ms | 25432 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2036 ms | 25176 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2037 ms | 25176 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 348 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |