Submission #321451

#	Time	Username	Problem	Language	Result	Execution time	Memory
321451		tjdgus4384	장애물 경기 (KOI16_dd)	C++14	100 / 100	94 ms	6848 KiB

dd

#include<bits/stdc++.h>
using namespace std;
int N, x, y, a, b, c;
set<pair<int, long long> > s;
vector<pair<int, pair<int, int> > > v;

int main(){
    scanf("%d", &N);
    scanf("%d %d", &x, &y);
    s.insert({x, 0});
    for(int i = 0;i < N;i++){
        scanf("%d %d %d", &a, &b, &c);
        v.push_back({a, {b, c}});
    }
    sort(v.begin(), v.end());
    for(int i = 0;i < N;i++){
        a = v[i].first;
        b = v[i].second.first;
        c = v[i].second.second;
        set<pair<int, long long> >::iterator it;
        it = s.lower_bound({b+1, 0});
        vector<pair<int, long long> > m1, m2;
        while(it != s.end()){
            int yt = (*it).first;
            if(yt >= c) break;
            long long len = (*it).second;
            m1.push_back({b, len+(long long)yt-(long long)b});
            m2.push_back({c, len+(long long)c-(long long)yt});
            set<pair<int, long long> >::iterator tmp = it;
            it++;
            s.erase(tmp);
        }
        if(!m1.empty()){
            sort(m1.begin(), m1.end());
            sort(m2.begin(), m2.end());
            s.insert(m1.front());
            s.insert(m2.front());
        }
    }
    set<pair<int, long long> >::iterator it;
    long long ans = 1e18, cnt = 0;
    vector<int> chk;
    it = s.begin();
    while(it != s.end()){
        if(ans == (*it).second){
            cnt++; chk.push_back((*it).first);
        }
        else if(ans > (*it).second){
            ans = (*it).second;
            cnt = 1; chk.clear(); chk.push_back((*it).first);
        }
        it++;
    }
    printf("%lld\n%d", ans+y, cnt);
    for(int i = 0;i < chk.size();i++){
        printf(" %d", chk[i]);
    }
    return 0;
}

Compilation message (stderr)

dd.cpp: In function 'int main()':
dd.cpp:54:20: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
   54 |     printf("%lld\n%d", ans+y, cnt);
      |                   ~^          ~~~
      |                    |          |
      |                    int        long long int
      |                   %lld
dd.cpp:55:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int i = 0;i < chk.size();i++){
      |                   ~~^~~~~~~~~~~~
dd.cpp:8:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    8 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
dd.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    9 |     scanf("%d %d", &x, &y);
      |     ~~~~~^~~~~~~~~~~~~~~~~
dd.cpp:12:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   12 |         scanf("%d %d %d", &a, &b, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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