Submission #1133258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133258		realpsdoingdamyoo	장애물 경기 (KOI16_dd)	C++20	100 / 100	118 ms	15036 KiB

dd

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef array<ll, 2> pii;
typedef array<ll, 3> tii;
typedef vector<pii> vpii;
typedef double lf;
#define V vector
#define PQ priority_queue
#define fastio; cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
#define vcin; for(int i=0; i<n; i++) cin >> v[i];
#define forf(i, s, e) for(ll i=s; i<e; i++)
#define forb(i, s, e) for(ll i=s-1; i>=e; i--)
#define pb push_back
#define sortv(v) sort(v.begin(), v.end())
#define sortc(v, cmp) sort(v.begin(), v.end(), cmp)
#define all(v) v.begin(), v.end()
const ll mod=1e9+7, MOD=998244353;
const vpii dir4={{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
const vpii dir8={{0, 1}, {1, 0}, {-1, 0}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
const ll inf=2147483647, linf=9223372036854775807;
const double pi=acos(-1), E=2.718281828459;
ll gcd(ll a, ll b){return b?gcd(b, a%b):a;}
#define cf; cout.flush();

// s : y, x, d
// v : x, sy, ey

int main() {
    //fastio;

    ll n; cin >> n;
    set<tii> s; V<tii> obs(n);
    ll sy, ex; cin >> sy >> ex;
    s.insert({sy, 0, 0});

    forf(i, 0, n) forf(j, 0, 3) cin >> obs[i][j];
    sortv(obs);

    forf(i, 0, n){
        auto it=s.lower_bound({obs[i][1], -1, -1});
        tii t=*it;
        tii sbest={obs[i][1], obs[i][0], obs[i][0]-t[1]+abs(obs[i][1]-t[0])+t[2]};
        tii ebest={obs[i][2], obs[i][0], obs[i][0]-t[1]+abs(obs[i][2]-t[0])+t[2]};
        while((*it)[0]<=obs[i][2] && it!=s.end()){
            //cout << "((";
            //forf(j, 0, 3) cout << (*it)[j] << " ";
            //cout << "))";
            tii t=*it;
            tii _sbest={obs[i][1], obs[i][0], obs[i][0]-t[1]+abs(obs[i][1]-t[0])+t[2]};
            tii _ebest={obs[i][2], obs[i][0], obs[i][0]-t[1]+abs(obs[i][2]-t[0])+t[2]};
            if(_sbest[2]<sbest[2]) sbest=_sbest;
            if(_ebest[2]<ebest[2]) ebest=_ebest;
            auto nit=next(it);
            s.erase(it); it=nit;
        }
        s.insert(sbest);
        s.insert(ebest);

        /*for(tii i : s){
            cout << "[";
            forf(j, 0, 3) cout << i[j] << " ";
            cout << "]";
        }
        cout << "\n";*/
    }
    vpii ans;
    for(tii t : s){
        if(ans.size()==0 || ans[0][1]>=t[2]+ex-t[1]){
            if(ans.size() && ans[0][1]>t[2]+ex-t[1]) ans.clear();
            ans.pb({t[0], t[2]+ex-t[1]});
        }
    }
    sortv(ans);
    cout << ans[0][1] << "\n" << ans.size() << " ";
    for(pii p : ans) cout << p[0] << " ";

    return 0;
}

Compilation message (stderr)

dd.cpp:12:9: warning: ISO C++11 requires whitespace after the macro name
   12 | #define fastio; cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
      |         ^~~~~~
dd.cpp:13:9: warning: ISO C++11 requires whitespace after the macro name
   13 | #define vcin; for(int i=0; i<n; i++) cin >> v[i];
      |         ^~~~
dd.cpp:26:9: warning: ISO C++11 requires whitespace after the macro name
   26 | #define cf; cout.flush();
      |         ^~

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