이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h" /** keep-include */
using namespace std;
#define rep(i, b, e) for(int i = (b); i <= (e); i++)
#define per(i, b, e) for(int i = (e); i >= (b); i--)
#define FOR(i, b, e) rep(i, b, (e) - 1)
#define SZ(x) int(x.size())
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
auto &operator<<(auto &o, pair<auto, auto> p) {
return o << "(" << p.st << ", " << p.nd << ")"; }
auto operator<<(auto &o, auto x)->decltype(end(x), o) {
o << "{"; int i=0; for(auto e: x) o << ", " + 2*!i++ << e;
return o << "}"; }
#ifdef LOCAL
#define deb(x...) cerr << "[" #x "]: ", [](auto...$) { \
((cerr << $ << "; "),...) << endl; }(x)
#else
#define deb(...)
#endif
const int K=19, N=3e5+5;
vector<pii> loty[N];
vector<int> id[N];
int nxt[K][N];
ll czas[K][N];
pair<int, ll> jump(int v, int t){
ll res=0;
for(int k=K-1; k>=0; k--){
if(t>=(1<<k)){
res+=czas[k][v];
v=nxt[k][v];
t-=(1<<v);
}
}
return mp(v, res);
}
void solve() {
int n, t;
cin>>n>>t;
vector<pair<pii, int> > co;
co.pb(mp(mp(0, 0), 0));
for(int i=1; i<n; i++){
int k;
cin>>k;
vector<pair<int, int> > V(k);
for(auto &j:V){
cin>>j.st>>j.nd;
}
sort(all(V));
vector<pii> V2;
for(auto &j:V){
while(V2.size() && V2.back().nd>=j.nd){
V.pop_back();
}
V2.pb(j);
}
k=V2.size();
for(int j=0; j<k; j++){
id[i].pb(co.size());
co.pb(mp(V2[j], i));
}
loty[i]=V2;
}
for(int j=1; j<co.size(); j++){
auto &[seg, i] = co[j];
if(i!=n-1){
auto it=lower_bound(all(loty[i+1]), mp(seg.nd, 0));
if(it==loty[i+1].end()){
it=loty[i+1].begin();
nxt[0][j]=id[i+1][it-loty[i+1].begin()];
czas[0][j]=it->nd-seg.nd+t;
deb(czas[0][j], it->nd, seg.nd,t);
}
else{
nxt[0][j]=id[i+1][it-loty[i+1].begin()];
czas[0][j]=it->nd-seg.nd;
}
}
deb(j, seg, i, co[nxt[0][j]], czas[0][j]);
}
for(int k=1; k<K; k++){
for(int i=1; i<co.size(); i++){
nxt[k][i]=nxt[k-1][nxt[k-1][i]];
czas[k][i]=czas[k-1][i]+czas[k-1][nxt[k-1][i]];
}
}
map<pair<int, int> , ll> old_ans;
int q;
cin>>q;
while(q--){
int l, r;
cin>>l>>r;
if(old_ans.find(mp(l, r))!=old_ans.end()){
cout<<old_ans[mp(l, r)]<<"\n";
continue;
}
ll ans=1e18;
for(int i=0; i<loty[l].size(); i++){
ll part=loty[l][i].nd-loty[l][i].st;
int lot=id[l][i];
deb(lot);
/*for(int j=l+1; j<r; j++){
part+=czas[0][lot];
lot=nxt[0][lot];
}*/
part+=jump(lot, r-l-1).nd;
deb(part);
ans=min(ans, part);
}
old_ans[mp(l, r)]=ans;
cout<<ans<<"\n";
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int tt = 1;
// cin >> tt;
FOR(te, 0, tt) solve();
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp:17:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
17 | auto &operator<<(auto &o, pair<auto, auto> p) {
| ^~~~
Main.cpp:17:32: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
17 | auto &operator<<(auto &o, pair<auto, auto> p) {
| ^~~~
Main.cpp:17:38: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
17 | auto &operator<<(auto &o, pair<auto, auto> p) {
| ^~~~
Main.cpp:19:17: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
19 | auto operator<<(auto &o, auto x)->decltype(end(x), o) {
| ^~~~
Main.cpp:19:26: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
19 | auto operator<<(auto &o, auto x)->decltype(end(x), o) {
| ^~~~
Main.cpp: In function 'void solve()':
Main.cpp:76:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for(int j=1; j<co.size(); j++){
| ~^~~~~~~~~~
Main.cpp:94:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for(int i=1; i<co.size(); i++){
| ~^~~~~~~~~~
Main.cpp:110:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for(int i=0; i<loty[l].size(); i++){
| ~^~~~~~~~~~~~~~~
# | 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... |