Submission #131799

#	Time	Username	Problem	Language	Result	Execution time	Memory
131799		tjdgus4384	장애물 경기 (KOI16_dd)	C++14	0 / 100	73 ms	65540 KiB

dd

#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 (stderr)

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);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 22
• Subtask 3: 0 / 29
• Subtask 4: 0 / 36