Submission #992920

#TimeUsernameProblemLanguageResultExecution timeMemory
99292079brueEscape Route 2 (JOI24_escape2)C++17
54 / 100
628 ms822120 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = 1e18; const int DEPTH = 17; struct segTree{ int minV[400002], minIdx[400002]; void init(int i, int l, int r, int *A){ if(l==r){ minV[i] = A[l], minIdx[i] = l; return; } int m = (l+r)>>1; init(i*2, l, m, A); init(i*2+1, m+1, r, A); if(minV[i*2] <= minV[i*2+1]) minV[i] = minV[i*2], minIdx[i] = minIdx[i*2]; else minV[i] = minV[i*2+1], minIdx[i] = minIdx[i*2+1]; } pair<int, int> query(int i, int l, int r, int s, int e){ if(r<s || e<l) return make_pair(INT_MAX, -1); if(s<=l && r<=e) return make_pair(minV[i], minIdx[i]); int m = (l+r)>>1; return min(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e)); } } tree; struct dat{ ll x, y; dat(){} dat(ll x, ll y): x(x), y(y){} bool operator<(const dat &r)const{ if(x != r.x) return x < r.x; return y > r.y; } bool operator<(const ll &r)const{ return x < r; } }; struct Query{ int l, r, idx; Query(){} Query(int l, int r, int idx): l(l), r(r), idx(idx){} }; int n, q, K; ll T; dat arr[100002], arrRev[100002]; int S[100002], E[100002], sz[100002], from[100002]; int nxtR[100002], dayR[100002], nxtL[100002], dayL[100002]; vector<int> childL[100002], childR[100002]; /// 왼쪽이 루트인 트리 / 오른쪽이 루트인 트리 vector<Query> queries[100002]; vector<ll> ql[100002]; ll ans[300002]; int listX[100002], listD[100002]; int pcnt = 0; void dfsL(int x){ listX[from[x]] = x; ql[x].reserve((int)queries[from[x]].size()); for(Query &p: queries[from[x]]){ ql[x].push_back((listD[from[x]] - listD[p.l]) * T + arr[x].x - arr[listX[p.l]].x); assert(++pcnt <= 50'000'000); } listD[from[x]+1] = listD[from[x]]; for(int y: childL[x]){ if(arrRev[x].x > arrRev[y].y) listD[from[x]+1]++; dfsL(y); if(arrRev[x].x > arrRev[y].y) listD[from[x]+1]--; } } void dfsR(int x){ listX[from[x]] = x; for(int i=0; i<(int)queries[from[x]].size(); i++){ Query p = queries[from[x]][i]; ll qlv = ql[x][i], qrv = (listD[from[x]] - listD[p.r-1]) * T + arr[listX[p.r-1]].y - arr[x].y; ans[p.idx] = min(ans[p.idx], qlv + qrv + arr[x].y - arr[x].x); } listD[from[x]-1] = listD[from[x]]; for(int y: childR[x]){ if(arr[x].x < arr[y].y) listD[from[x]-1]++; dfsR(y); if(arr[x].x < arr[y].y) listD[from[x]-1]--; } } int main(){ scanf("%d %lld", &n, &T); for(int i=1; i<n; i++){ int s; scanf("%d", &s); vector<dat> vec; vec.resize(s); for(int j=0; j<s; j++) scanf("%lld %lld", &vec[j].x, &vec[j].y); sort(vec.begin(), vec.end()); vector<dat> vec2; for(int j=0; j<s; j++){ while(!vec2.empty() && vec2.back().y >= vec[j].y) vec2.pop_back(); vec2.push_back(vec[j]); } sz[i] = (int)vec2.size(); S[i] = E[i-1] + 1, E[i] = S[i] + sz[i] - 1; for(int j=0; j<sz[i]; j++) arr[S[i]+j] = vec2[j]; for(int j=S[i]; j<=E[i]; j++) arrRev[j] = dat(arr[j].y, arr[j].x), from[j] = i; } tree.init(1, 1, n-1, sz); for(int d=1; d<=n-2; d++){ for(int i=S[d]; i<=E[d]; i++){ int L = S[d+1], R = E[d+1]; if(arr[R].x >= arr[i].y) nxtR[i] = lower_bound(arr+L, arr+R+1, dat(arr[i].y, INF)) - arr; else nxtR[i] = L, dayR[i] = 1; childR[nxtR[i]].push_back(i); } } for(int d=3; d<=n; d++){ for(int i=S[d-1]; i<=E[d-1]; i++){ int L = S[d-2], R = E[d-2]; if(arrRev[L].x <= arrRev[i].y) nxtL[i] = upper_bound(arrRev+L, arrRev+R+1, dat(arrRev[i].y, -INF)) - arrRev - 1; else nxtL[i] = R, dayL[i] = 1; childL[nxtL[i]].push_back(i); } } scanf("%d", &q); for(int i=1; i<=q; i++){ int l, r; scanf("%d %d", &l, &r); int minIdx = tree.query(1, 1, n-1, l, r-1).second; queries[minIdx].push_back(Query(l, r, i)); ans[i] = LLONG_MAX; } listD[1] = 0; for(int i=S[1]; i<=E[1]; i++) dfsL(i); listD[n-1] = 0; for(int i=S[n-1]; i<=E[n-1]; i++) dfsR(i); for(int i=1; i<=q; i++) printf("%lld\n", ans[i]); }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:94:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |     scanf("%d %lld", &n, &T);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         scanf("%d", &s);
      |         ~~~~~^~~~~~~~~~
Main.cpp:101:37: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         for(int j=0; j<s; j++) scanf("%lld %lld", &vec[j].x, &vec[j].y);
      |                                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:135:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
Main.cpp:138:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |         scanf("%d %d", &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...