이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
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;
}
};
int n; ll T;
vector<dat> arr[100002];
vector<dat> arrRev[100002];
int sz[100002];
vector<ll> sps[100002][20], spsRev[100002][20];
struct Query{
int l, r, idx;
Query(){}
Query(int l, int r, int idx): l(l), r(r), idx(idx){}
};
int q;
vector<Query> queries[100002];
ll ans[300002];
int lRecent[100002], rRecent[100002];
vector<ll> lVec[100002], rVec[100002];
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());
for(int j=0; j<s; j++){
while(!arr[i].empty() && arr[i].back().y >= vec[j].y) arr[i].pop_back();
arr[i].push_back(vec[j]);
}
sz[i] = (int)arr[i].size();
arrRev[i+1] = arr[i];
for(dat &p: arrRev[i+1]) swap(p.x, p.y);
}
tree.init(1, 1, n-1, sz);
/// sps 채우기
for(int i=1; i<n; i++) for(int j=0; j<sz[i]; j++) sps[i][0].push_back(arr[i][j].y);
for(int d=1; d<20; d++){
for(int i=1; i+(1<<d)<=n; i++) for(int j=0; j<sz[i]; j++){
ll vT = sps[i][d-1][j], vtime = vT % T; vT -= vtime;
int nxtX = i + (1<<(d-1));
ll nxtT;
if(arr[nxtX].back().x >= vtime)
nxtT = vT + sps[nxtX][d-1][lower_bound(arr[nxtX].begin(), arr[nxtX].end(), dat(vtime, INF)) - arr[nxtX].begin()];
else nxtT = vT + T + sps[nxtX][d-1][0];
sps[i][d].push_back(nxtT);
}
}
/// spsRev 채우기
for(int i=2; i<=n; i++) for(int j=0; j<sz[i-1]; j++) spsRev[i][0].push_back(T-arrRev[i][j].y);
for(int d=1; d<20; d++){
for(int i=n; i-(1<<d)>=1; i--) for(int j=0; j<sz[i-1]; j++){
ll vT = spsRev[i][d-1][j], vtime = vT % T; vT -= vtime;
int nxtX = i - (1<<(d-1));
ll nxtT;
if(arrRev[nxtX][0].x <= T - vtime)
nxtT = vT + spsRev[nxtX][d-1][upper_bound(arrRev[nxtX].begin(), arrRev[nxtX].end(), dat(T-vtime, -INF)) - arrRev[nxtX].begin() - 1];
else nxtT = vT + T + spsRev[nxtX][d-1][sz[nxtX-1]-1];
spsRev[i][d].push_back(nxtT);
}
}
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));
}
ll qsum = 0;
for(int m=1; m<n; m++) qsum += ll(sz[m]) * (ll)queries[m].size();
assert(qsum <= 200'000'000LL);
qsum = 0;
for(int m=1; m<n; m++){
for(Query p: queries[m]){
int L = p.l, R = p.r;
if(lRecent[L] != m) qsum += sz[m], lRecent[L] = m;
if(rRecent[R] != m) qsum += sz[m], rRecent[R] = m;
}
}
assert(qsum <= 5'000'000);
for(int i=1; i<=n; i++) lRecent[i] = rRecent[i] = 0;
for(int m=1; m<n; m++){
for(Query p: queries[m]){
int L = p.l, R = p.r;
if(lRecent[L] != m){
lRecent[L] = m;
lVec[L].clear();
for(int i=0; i<sz[m]; i++){
ll nowT = T - arrRev[m+1][i].x; int diff = m+1 - L, nowX = m+1;
for(int j=0; j<20; j++) if((diff>>j)&1){
ll vtime = nowT % T, vT = nowT - vtime, nxtT;
if(arrRev[nowX][0].x <= T - vtime)
nxtT = vT + spsRev[nowX][j][upper_bound(arrRev[nowX].begin(), arrRev[nowX].end(), dat(T-vtime, -INF)) - arrRev[nowX].begin() - 1];
else nxtT = vT + T + spsRev[nowX][j][sz[nowX-1]-1];
nowT = nxtT, nowX -= 1<<j;
}
lVec[L].push_back(nowT);
}
}
if(rRecent[R] != m){
rRecent[R] = m;
rVec[R].clear();
for(int i=0; i<sz[m]; i++){
ll nowT = arr[m][i].x; int diff = R-m, nowX = m;
for(int j=0; j<20; j++) if((diff>>j)&1){
ll vtime = nowT % T, vT = nowT - vtime, nxtT;
if(arr[nowX].back().x >= vtime)
nxtT = vT + sps[nowX][j][lower_bound(arr[nowX].begin(), arr[nowX].end(), dat(vtime, INF)) - arr[nowX].begin()];
else nxtT = vT + T + sps[nowX][j][0];
nowT = nxtT, nowX += 1<<j;
}
rVec[R].push_back(nowT);
}
}
ll minV = LLONG_MAX;
for(int i=0; i<sz[m]; i++){
minV = min(minV, lVec[L][i] - (T - arrRev[m+1][i].x) + rVec[R][i] - arr[m][i].x - (arr[m][i].y - arr[m][i].x));
}
ans[p.idx] = minV;
}
}
for(int i=1; i<=q; i++) printf("%lld\n", ans[i]);
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'int main()':
Main.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
65 | scanf("%d %lld", &n, &T);
| ~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | scanf("%d", &s);
| ~~~~~^~~~~~~~~~
Main.cpp:72:37: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
72 | for(int j=0; j<s; j++) scanf("%lld %lld", &vec[j].x, &vec[j].y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:114:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
114 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
Main.cpp:117:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
117 | scanf("%d %d", &l, &r);
| ~~~~~^~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |