#include<bits/stdc++.h>
using namespace std;
vector<pair<int, pair<int, int> > > v;
int seg[20000001], up[100001], down[100001];
int seg1[20000001], ans = 1000000000, n;
vector<int> printans;
void update(int left, int right, int node, int start, int end, int key, int index){
if(left > end || start > right) return;
if(start <= left && right <= end) {
if(seg[node] > key) seg1[node] = index;
seg[node] = min(seg[node], key);
}
if(left == right) return;
int mid = (left+right)/2;
update(left, mid, node*2, start, end, key, index);
update(mid + 1, right, node*2+1, start, end, key, index);
}
int get(int left, int right, int node, int key){
if(left > key || key > right) return 1000000000;
if(left == key && key == right) return seg[node];
int mid = (left+right)/2;
return min(get(left, mid, node*2, key), get(mid+1, right, node*2+1, key));
}
int get1(int left, int right, int node, int key){
if(left > key || key > right) return 1000000000;
if(left == key && key == right) return seg1[node];
int mid = (left+right)/2;
return min(get1(left, mid, node*2, key), get1(mid+1, right, node*2+1, key));
}
void dfs(int x, int y, int c){
if(c > ans) return;
if(x == n){
if(ans > c){
ans = c;
printans.clear();
printans.push_back(y);
}
else printans.push_back(y);
return;
}
dfs(up[x], v[x].second.second, c + v[x].second.second - y + v[up[x]].first - v[x].first);
dfs(down[x], v[x].second.first, c + y - v[x].second.first + v[down[x]].first - v[x].first);
}
int main(){
int xend, ystart, x, y1, y2;
scanf("%d", &n);
scanf("%d %d", &ystart, &xend);
for(int i = 0;i < n;i++){
scanf("%d %d %d", &x, &y1, &y2);
v.push_back({x, {y1, y2}});
}
v.push_back({xend, {0, 8000000}});
for(int i = 1;i <= 20000000;i++) {seg[i] = xend;seg1[i] = n;}
sort(v.begin(), v.end());
for(int i = n - 1;i >= 0;i--){
x = v[i].first;
y1 = v[i].second.first;
y2 = v[i].second.second;
up[i] = get1(0, 8000000, 1, y2);
down[i] = get1(0, 8000000, 1, y1);
update(0, 8000000, 1, y1 + 1, y2 - 1, x, i);
}
y1 = get1(0, 8000000, 1, ystart);
dfs(y1, ystart, v[y1].first);
printans.erase(unique(printans.begin(), printans.end()), printans.end());
sort(printans.begin(), printans.end());
printf("%d\n%d", ans, printans.size());
for(int i = 0;i < printans.size();i++) printf(" %d", printans[i]);
}
Compilation message
dd.cpp: In function 'int main()':
dd.cpp:72:42: warning: format '%d' expects argument of type 'int', but argument 3 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
printf("%d\n%d", ans, printans.size());
~~~~~~~~~~~~~~~^
dd.cpp:73:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < printans.size();i++) printf(" %d", printans[i]);
~~^~~~~~~~~~~~~~~~~
dd.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
dd.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &ystart, &xend);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
dd.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &x, &y1, &y2);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
73 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
73 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
73 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
73 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
