QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#852996#9730. Elevator IIucup-team5243#AC ✓108ms10320kbC++2317.0kb2025-01-11 15:10:392025-01-11 15:10:47

Judging History

你现在查看的是最新测评结果

  • [2025-01-11 15:10:47]
  • 评测
  • 测评结果:AC
  • 用时:108ms
  • 内存:10320kb
  • [2025-01-11 15:10:39]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#ifndef LOCAL_TEST
#pragma GCC target ("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#endif // LOCAL_TEST

using ll = long long;
using i128 = __int128_t;
using str = string;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using vi = vector<int>;  using vvi = vector<vi>; using vvvi = vector<vvi>;
using vl = vector<ll>;  using vvl = vector<vl>; using vvvl = vector<vvl>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vc = vector<char>; using vvc = vector<vc>; using vvvc = vector<vvc>;
using vd = vector<double>; using vvd = vector<vd>; using vvvd = vector<vvd>;
using vs = vector<string>; using vvs = vector<vector<string>>; using vvvs = vector<vector<vector<string>>>;

template<typename T> vector<vector<T>> vv(int h, int w, T val = T()) { return vector(h, vector<T>(w, val)); }
template<typename T> vector<vector<vector<T>>> vvv(int h1, int h2, int h3, T val = T()) { return vector(h1, vector(h2, vector<T>(h3, val))); }
template<typename T> vector<vector<vector<vector<T>>>> vvvv(int h1, int h2, int h3, int h4, T val = T()) { return vector(h1, vector(h2, vector(h3, vector<T>(h4, val)))); }

template <class T> using priority_queue_min = priority_queue<T, vector<T>, greater<T>>;

constexpr double PI = 3.14159265358979323;
constexpr int INF = 100100111; constexpr ll INFL = 3300300300300300491LL;
float EPS = 1e-8; double EPSL = 1e-10;


struct Nyan { Nyan() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } nyan;

#define all(a) (a).begin(), (a).end()
#define len(x) ((ll)(x).size())
#define sz(x) ((ll)(x).size())
#define rep1(n) for(ll dummy_iter = 0LL; dummy_iter < n; ++dummy_iter) // 0,1,...,n-1
#define rep2(i, n) for(ll i = 0LL, i##_counter = 0LL; i##_counter < ll(n); ++(i##_counter), (i) = i##_counter) // i=0,1,...,n-1
#define rep3(i, s, t) for(ll i = ll(s), i##_counter = ll(s); i##_counter < ll(t); ++(i##_counter), (i) = (i##_counter)) // i=s,s+1,...,t-1
#define rep4(i, s, t, step) for(ll i##_counter = step > 0 ? ll(s) : -ll(s), i##_end = step > 0 ? ll(t) : -ll(t), i##_step = abs(step), i = ll(s); i##_counter < i##_end; i##_counter += i##_step, i = step > 0 ? i##_counter : -i##_counter) // i=s,s+step,...,<t
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define repe(a, v) for(auto&& a : (v)) // iterate over all elements in v
#define repc(a, v) for(const auto& a : (v)) // iterate over all elements in v
#define smod(n, m) ((((n) % (m)) + (m)) % (m))
#define sdiv(n, m) (((n) - smod(n, m)) / (m))
#define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());}

int Yes(bool b=true) { cout << (b ? "Yes\n" : "No\n"); return 0; };
int YES(bool b=true) { cout << (b ? "YES\n" : "NO\n"); return 0; };
int No(bool b=true) {return Yes(!b);};
int NO(bool b=true) {return YES(!b);};

template<typename T, size_t N> T max(array<T, N>& a) { return *max_element(all(a)); };
template<typename T, size_t N> T min(array<T, N>& a) { return *min_element(all(a)); };
template<typename T> T max(vector<T>& a) { return *max_element(all(a)); };
template<typename T> T min(vector<T>& a) { return *min_element(all(a)); };
template<typename T> vector<T> vec_slice(const vector<T>& a, int l, int r) { vector<T> rev; rep(i, l, r) rev.push_back(a[i]); return rev; };
template<typename T> vector<T> vec_slice(const vector<T>&& a, int l, int r) { vector<T> rev; rep(i, l, r) rev.push_back(a[i]); return rev; };
template<typename T> T sum(vector<T>& a, T zero = T(0)) { T rev = zero; rep(i, sz(a)) rev += a[i]; return rev; };
template<typename T> T sum(vector<T>&& a, T zero = T(0)) { T rev = zero; rep(i, sz(a)) rev += a[i]; return rev; };


template <class T> inline vector<T>& operator--(vector<T>& v) { repe(x, v) --x; return v; }
template <class T> inline vector<T>& operator++(vector<T>& v) { repe(x, v) ++x; return v; }

ll powll(ll a, ll n) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = (res * a);
        if (n > 1) a = (a * a);
        n >>= 1;
    }
    return res;
}
ll powm32(ll a, ll n, int mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = (res * a) % mod;
        if (n > 1) a = (a * a) % mod;
        n >>= 1;
    }
    return res % mod;
}
ll powm64(i128 a,i128 n,ll mod){
    i128 res = 1;
    while (n > 0) {
        if (n & 1) res = (res * a) % mod;
        if (n > 1) a = (a * a) % mod;
        n >>= 1;
    }
    return res % mod;
}
ll sqrtll(ll x) {
    assert(x >= 0);
    ll rev = sqrt(x);
    while(rev * rev > x) --rev;
    while((rev+1) * (rev+1)<=x) ++rev;
    return rev;
}

template <class T> inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; }
template <class T> inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; }

template <class T, class U> inline istream& operator>>(istream& is, pair<T, U>& p);
template <class T> inline istream& operator>>(istream& is, vector<T>& v);
template <class T, class U> inline ostream& operator<<(ostream& os, const pair<T, U>& p);
template <class T> inline ostream& operator<<(ostream& os, const vector<T>& v);
template <typename T, typename S> ostream &operator<<(ostream &os, const map<T, S> &mp);
template <typename T> ostream &operator<<(ostream &os, const set<T> &st);
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &st);
template <typename T> ostream &operator<<(ostream &os, const unordered_set<T> &st);
template <typename T> ostream &operator<<(ostream &os, deque<T> q);
template <class T, class Container, class Compare> ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> pq);

template <class T, class U> inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template <class T> inline istream& operator>>(istream& is, vector<T>& v) { repe(x, v) is >> x; return is; }
template <class T, class U> inline ostream& operator<<(ostream& os, const pair<T, U>& p) { os << p.first << " " << p.second; return os; }
template <class T> inline ostream& operator<<(ostream& os, const vector<T>& v) { rep(i, sz(v)) { os << v.at(i); if (i != sz(v) - 1) os << " "; } return os; }
template <typename T, typename S> ostream &operator<<(ostream &os, const map<T, S> &mp) { for (auto &[key, val] : mp) { os << key << ":" << val << " "; } return os; }
template <typename T> ostream &operator<<(ostream &os, const set<T> &st) { auto itr = st.begin(); for (int i = 0; i < (int)st.size(); i++) { os << *itr << (i + 1 != (int)st.size() ? " " : ""); itr++; } return os; }
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &st) { auto itr = st.begin(); for (int i = 0; i < (int)st.size(); i++) { os << *itr << (i + 1 != (int)st.size() ? " " : ""); itr++; } return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_set<T> &st) { ll cnt = 0; for (auto &e : st) { os << e << (++cnt != (int)st.size() ? " " : ""); } return os; }
template <typename T> ostream &operator<<(ostream &os, deque<T> q) { while (q.size()) { os << q.front(); q.pop_front(); if (q.size()) os << " "; } return os; }
template <class T, class Container, class Compare> ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> pq) { while (pq.size()) { os << pq.top() << " "; pq.pop(); } return os; }
#define dout(x) cout << fixed << setprecision(10) << x << endl

#define read1(a) cin >> a;
#define read2(a, b) cin >> a >> b;
#define read3(a, b, c) cin >> a >> b >> c;
#define read4(a, b, c, d) cin >> a >> b >> c >> d;
#define read5(a, b, c, d, e) cin >> a >> b >> c >> d >> e;
#define read6(a, b, c, d, e, f) cin >> a >> b >> c >> d >> e >> f;
#define read7(a, b, c, d, e, f, g) cin >> a >> b >> c >> d >> e >> f >> g;
#define read8(a, b, c, d, e, f, g, h) cin >> a >> b >> c >> d >> e >> f >> g >> h;

#define overload_read(a, b, c, d, e, f, g, h, i, ...) i
#define read(...) overload_read(__VA_ARGS__,read8,read7,read6,read5,read4,read3,read2,read1)(__VA_ARGS__)

#ifdef LOCAL_TEST
#define inner_output1(a) cout << a << endl;cerr << "[OUTPUT #" << __LINE__ << "] " << a << endl;
#define inner_output2(a, b) cout << a << " " << b << endl;cerr << "[OUTPUT #" << __LINE__ << "] " << a << " " <<b << endl;
#define inner_output3(a, b, c) cout << a << " " << b << " " << c << endl;cerr << "[OUTPUT #" << __LINE__ << "] " << a << " " << b << " " << c << endl;
#define inner_output4(a, b, c, d) cout << a << " " << b << " " << c << " " << d << endl;cerr << "[OUTPUT #" << __LINE__ << "] " << a << " " << b << " " << c << " " << d << endl;
#define inner_output5(a, b, c, d, e) cout << a << " " << b << " " << c << " " << d << " " << e << endl;cerr << "[OUTPUT #" << __LINE__ << "] " << a << " " << b << " " << c << " " << d << " " << e << endl;
#define inner_output6(a, b, c, d, e, f) cout << a << " " << b << " " << c << " " << d << " " << e << " " << f << endl;cerr << "[OUTPUT #" << __LINE__ << "] " << a << " " << b << " " << c << " " << d << " " << e << " " << f << endl;
#define inner_output7(a, b, c, d, e, f, g) cout << a << " " << b << " " << c << " " << d << " " << e << " " << f << " " << g << endl;cerr << "[OUTPUT #" << __LINE__ << "] " << a << " " << b << " " << c << " " << d << " " << e << " " << f << " " << g << endl;
#define inner_output8(a, b, c, d, e, f, g, h) cout << a << " " << b << " " << c << " " << d << " " << e << " " << f << " " << g << " " << h << endl;cerr << "[OUTPUT #" << __LINE__ << "] " << a << " " << b << " " << c << " " << d << " " << e << " " << f << " " << g << " " << h << endl;

#else

#define inner_output1(a) cout << a << endl;
#define inner_output2(a, b) cout << a << " " << b << endl;
#define inner_output3(a, b, c) cout << a << " " << b << " " << c << endl;
#define inner_output4(a, b, c, d) cout << a << " " << b << " " << c << " " << d << endl;
#define inner_output5(a, b, c, d, e) cout << a << " " << b << " " << c << " " << d << " " << e << endl;
#define inner_output6(a, b, c, d, e, f) cout << a << " " << b << " " << c << " " << d << " " << e << " " << f << endl;
#define inner_output7(a, b, c, d, e, f, g) cout << a << " " << b << " " << c << " " << d << " " << e << " " << f << " " << g << endl;
#define inner_output8(a, b, c, d, e, f, g, h) cout << a << " " << b << " " << c << " " << d << " " << e << " " << f << " " << g << " " << h << endl;

#endif
#define overload_inner_output(a, b, c, d, e, f, g, h, i, ...) i
#define out(...) overload_inner_output(__VA_ARGS__,inner_output8,inner_output7,inner_output6,inner_output5,inner_output4,inner_output3,inner_output2,inner_output1)(__VA_ARGS__)

#define ii(...) ll __VA_ARGS__; read(__VA_ARGS__)
#define si(...) string __VA_ARGS__; read(__VA_ARGS__)
#define ci(...) char __VA_ARGS__; read(__VA_ARGS__)
#define di(...) double __VA_ARGS__; read(__VA_ARGS__)
#define li(name,size); vector<ll> name(size); read(name)
#define lli(name,H,W); vector name(H,vector<ll>(W));rep(i,H) cin >> name[i];


#ifdef LOCAL_TEST
#define inner_debug1(a) cerr << "[DEBUG#" << __LINE__ << "] " << #a << " = " << a << endl;
#define inner_debug2(a, b) cerr << "[DEBUG#" << __LINE__ << "] "<< #a << " = " << a << ", " << #b << " = " << b << endl;
#define inner_debug3(a, b, c) cerr << "[DEBUG#" << __LINE__ << "] "<< #a << " = " << a << ", " << #b << " = " << b << ", " << #c << " = " << c << endl;
#define inner_debug4(a, b, c, d) cerr << "[DEBUG#" << __LINE__ << "] "<< #a << " = " << a << ", " << #b << " = " << b << ", " << #c << " = " << c << ", " << #d << " = " << d << endl;
#define inner_debug5(a, b, c, d, e) cerr << "[DEBUG#" << __LINE__ << "] "<< #a << " = " << a << ", " << #b << " = " << b << ", " << #c << " = " << c << ", " << #d << " = " << d << ", " << #e << " = " << e << endl;
#define inner_debug6(a, b, c, d, e, f) cerr << "[DEBUG#" << __LINE__ << "] "<< #a << " = " << a << ", " << #b << " = " << b << ", " << #c << " = " << c << ", " << #d << " = " << d << ", " << #e << " = " << e << ", " << #f << " = " << f << endl;
#define inner_debug7(a, b, c, d, e, f, g) cerr << "[DEBUG#" << __LINE__ << "] "<< #a << " = " << a << ", " << #b << " = " << b << ", " << #c << " = " << c << ", " << #d << " = " << d << ", " << #e << " = " << e << ", " << #f << " = " << f << ", " << #g << " = " << g << endl;
#define inner_debug8(a, b, c, d, e, f, g, h) cerr << "[DEBUG#" << __LINE__ << "] "<< #a << " = " << a << ", " << #b << " = " << b << ", " << #c << " = " << c << ", " << #d << " = " << d << ", " << #e << " = " << e << ", " << #f << " = " << f << ", " << #g << " = " << g << ", " << #h << " = " << h << endl;

#define overload_inner_debug(a, b, c, d, e, f, g, h, i, ...) i
#define debug(...) overload_inner_debug(__VA_ARGS__,inner_debug8,inner_debug7,inner_debug6,inner_debug5,inner_debug4,inner_debug3,inner_debug2,inner_debug1)(__VA_ARGS__)

#else
#define debug(...);
#endif // LOCAL_TEST


inline ll ctz(ll x) { return __builtin_ctzll(x);}
inline ll clz(ll x) { return __builtin_clzll(x);}
inline ll popcount(ll x) { return __builtin_popcountll(x);}
inline bool inrange(ll x, ll a, ll b) { return a <= x && x < b; }
template <typename T> inline ll findll(vector<T>& v, T x) { auto tmp = find(all(v), x);if(tmp == v.end()){return -1;}else{return distance(v.begin(),tmp); }}
inline ll findll(string& s, char x) { auto tmp = find(all(s), x);if(tmp == s.end()){return -1;}else{return distance(s.begin(),tmp); }}
inline ll ceildiv(ll x,ll y){return (x+y-1)/y;}


#define allit(a,pred) [&]{repc(it,a){if(!(pred)) return false;}return true;}()
#define anyit(a,pred) [&]{repc(it,a){if((pred)) return true;}return false;}()

#define mapit(a, pred) ([&]() { \
    decltype(a)::value_type it; \
    vector<decltype(pred)> result_mapit(a.size()); \
    rep(idx,a.size()){\
        decltype(a)::value_type& it = a[idx];\
        result_mapit[idx] = pred;\
    }\
    return result_mapit; \
})()

#define filterit(a, pred) ([&]() { \
    decltype(a) result_filterit; \
    rep(idx,a.size()){\
        decltype(a)::value_type& it = a[idx];\
        if(pred){\
            result_filterit.push_back(it);\
        }\
    }\
    return result_filterit; \
})()

#define applyit(a, pred) { \
    rep(idx,a.size()){\
        decltype(a)::value_type& it = a[idx];\
        a[idx] = pred;\
    }\
}

#define countit(a, pred) ([&]() { \
    ll result_countit = 0; \
    rep(idx,a.size()){\
        decltype(a)::value_type& it = a[idx];\
        if(pred){\
            result_countit++;\
        }\
    }\
    return result_countit; \
})()

#define sortByIt(a,pred) {\
    sort(all(a),[&](const decltype(a)::value_type& left_value, const decltype(a)::value_type& right_value){auto it = left_value;auto x_value = pred;it = right_value;auto y_value = pred;return x_value<y_value;});\
}

ll minIndex(vector<ll>& a) {
    ll minIndex = 0;
    rep(i, 1, sz(a)) {
        if (a[i] < a[minIndex]) {
            minIndex = i;
        }
    }
    return minIndex;
}

ll maxIndex(vector<ll>& a) {
    ll maxIndex = 0;
    rep(i, 1, sz(a)) {
        if (a[i] > a[maxIndex]) {
            maxIndex = i;
        }
    }
    return maxIndex;
}

template<typename T> vector<T> sorted(vector<T> X){
    sort(all(X));
    return X;
}

vector<string> split(const string& s,char c){
    vector<string> res;
    res.push_back("");
    repc(a,s){
        if(a==c){
            res.push_back("");
        }else{
            res.back() += a;
        }
    }
    return res;
}

void solve(){
    ii(N,F);
    ll now = F;
    priority_queue_min<tuple<ll,ll,ll>> pq1;
    priority_queue<pll> pq2;
    ll mx = now;
    vl ans;
    vb alr(N,false);
    ll cost = 0;
    rep(i,N){
        ii(L,R);
        pq1.push({L,R,i});
        cost += R-L;
        chmax(mx,R);
    }
    while(!pq1.empty()){
        auto [L,R,idx] = pq1.top();
        if(L > now) break;
        pq1.pop();
        pq2.push({R,idx});
    }

    while(now!=mx){
        debug(now);
        debug(pq2);
        if(!pq2.empty()){
            auto [R,idx] = pq2.top();
            if(now < R){
                pq2.pop();
                alr[idx] = true;
                ans.push_back(idx+1);
                now = R;
                while(!pq1.empty()){
                    auto [L,R,idx] = pq1.top();
                    if(L > now) break;
                    pq1.pop();
                    pq2.push({R,idx});
                }
                continue;
            }
        }
        auto [L,R,idx] = pq1.top();pq1.pop();
        alr[idx] = true;
        ans.push_back(idx+1);
        cost += L-now;
        now = R;
        while(!pq1.empty()){
            auto [L,R,idx] = pq1.top();
            if(L > now) break;
            pq1.pop();
            pq2.push({R,idx});
        }
    }
    while(!pq1.empty()){
        auto [L,R,idx] = pq1.top();
        if(L > now) break;
        pq1.pop();
        pq2.push({R,idx});
    }
    while(!pq2.empty()){
        auto [R,idx] = pq2.top();pq2.pop();
        ans.push_back(idx+1);
    }
    out(cost);
    out(ans);
}

int main(){
    ii(T);
    rep(T) solve();
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3540kb

input:

2
4 2
3 6
1 3
2 7
5 6
2 5
2 4
6 8

output:

11
3 4 1 2
5
2 1

result:

ok ok 2 cases (2 test cases)

Test #2:

score: 0
Accepted
time: 59ms
memory: 3816kb

input:

6100
19 52
51 98
2 83
40 58
96 99
39 55
72 94
15 17
4 15
48 99
2 99
77 78
35 77
44 62
79 81
30 31
1 48
48 76
68 99
60 66
6 19
44 53
64 92
17 28
67 98
9 99
40 65
16 27
99 100
15 56
4 6
24 97
84 96
47 49
37 38
77 79
13 40
13 92
71 100
47 93
90 91
72 81
15 48
32 71
19 17
95 99
10 23
18 100
90 93
52 92
...

output:

524
10 18 9 4 1 6 2 14 11 12 17 19 13 3 5 16 15 7 8
194
5 4 2 6 1 3
397
4 11 1 5 12 10 13 14 8 16 2 6 15 9 7 3
733
7 3 10 1 8 6 4 17 5 16 13 11 15 12 18 14 9 19 2
244
3 2 8 6 12 5 4 14 10 11 9 1 15 13 7
422
18 1 6 11 10 2 7 13 9 12 4 20 14 5 15 19 8 16 3 17
104
4 1 3 2
187
4 8 3 1 2 6 7 5 9 10
117
2...

result:

ok ok 6100 cases (6100 test cases)

Test #3:

score: 0
Accepted
time: 108ms
memory: 10232kb

input:

3
100000 9859
150464 951410
637107 897197
236268 936879
353406 403927
511229 999416
861211 958428
186246 446149
162388 805753
449016 817386
147119 604340
579101 926848
958992 987299
859662 907007
507058 690951
719158 856587
789149 927957
691705 707085
694110 845505
192759 616586
905489 935507
937041...

output:

24903933702
92856 65801 39096 51617 33773 65474 94722 13509 21862 12929 87576 17341 15727 27729 11792 2606 55052 50887 48077 72396 33512 98442 16861 69859 42944 15997 66434 56377 59405 41121 7904 40847 9663 68634 34470 19087 50759 37212 24530 10095 70457 23408 6562 96796 55563 25733 93686 74144 2850...

result:

ok ok 3 cases (3 test cases)

Test #4:

score: 0
Accepted
time: 95ms
memory: 10052kb

input:

3
100000 932101
80818 80823
538842 538844
406812 406818
625053 625054
511066 511073
667363 667365
527022 527023
621329 621331
855832 855852
796168 796169
268927 268929
650891 650895
312793 312794
873256 873260
424896 424929
266271 266272
902201 902209
842863 842864
361599 361610
647851 647855
148132...

output:

986597
82641 30352 11990 41160 74602 95031 10872 13641 70364 69688 83583 94175 77157 82305 60601 21546 21059 98950 61273 47916 9311 25865 48329 29951 79449 26301 33491 96045 59186 89170 37084 58554 99074 38280 78061 69175 74069 26606 30169 81023 72809 43957 11035 22681 57154 73949 1545 46747 26464 2...

result:

ok ok 3 cases (3 test cases)

Test #5:

score: 0
Accepted
time: 98ms
memory: 10320kb

input:

3
100000 375117879
637628712 637644704
788784579 788792294
804734775 804734822
332639566 332642798
143113598 143114045
132119073 132122341
684483097 684513821
484676670 484678332
661667340 661668818
777865379 777870254
142495696 142495995
101735856 101740588
906481102 906481965
360087766 360091064
1...

output:

872643717
43549 34676 31878 49124 12077 8140 13605 76831 10834 96613 83688 46028 65944 14511 56152 84791 1759 60404 73244 38124 93732 74294 8688 64153 56500 39213 27938 93350 21680 36926 8295 8832 69685 1025 22233 14796 83881 83105 72820 95432 90168 29163 20496 4937 51441 96515 46657 82775 90528 380...

result:

ok ok 3 cases (3 test cases)

Extra Test:

score: 0
Extra Test Passed