Submission #858640

#	Time	Username	Problem	Language	Result	Execution time	Memory
858640		resting	Overtaking (IOI23_overtaking)	C++17	19 / 100	9 ms	1112 KiB

overtaking

#include <bits/stdc++.h>

using namespace std;
#define int long long

#define ff first
#define ss second

set<pair<int, int>> restriction; // if "starts after a", has to "end after b" yk

int x, l;
void init(int32_t L, int32_t N, std::vector<long long> T, std::vector<int32_t> W, int32_t X, int32_t M, std::vector<int32_t> S)
{
    restriction = {};
    x = X; l = L;
    vector<vector<pair<int, int>>> restrictions(M);// yes
    vector<pair<int, int>> cur;
    for (int i = 0; i < N; i++) if (W[i] > X) cur.push_back({ T[i], W[i] - X });
    for (int i = 0; i < M-1; i++) {
        sort(cur.begin(), cur.end());
        vector<pair<int, int>> res;
        const int T = cur.size();
        for (int j = 0; j < T; j++) 
            res.push_back({ cur[j].ff + cur[j].ss * (S[i + 1] - S[i]), cur[j].ss });
        for (int j = 0; j < T - 1; j++) 
            if (res[j].ff > res[j + 1].ff) 
                res[j + 1].ff = res[j].ff;
        int p  = -1;
        for (int j = 0; j < T; j++) {
            if(res[j].ff != p){
                if(j + 1 == T || cur[j].ff != cur[j+1].ff){
                    p = res[j].ff;
                    restrictions[i].push_back({ cur[j].ff+1, res[j].ff }); //start, end
                }
            }
        }
        for(int j = 1; j < restrictions[i].size(); j++){
            assert(restrictions[i][j].first > restrictions[i][j-1].first);
            assert(restrictions[i][j].second > restrictions[i][j-1].second);
        }

        swap(res, cur);
    }
    for (int i = 0; i < M; i++) {
        reverse(restrictions[i].begin(), restrictions[i].end());
        //cout<<"i: "<<i<<endl;
        //for(auto &x : restriction)
        //cout<<x.first<<" "<<x.second<<endl;
        for(auto x : restrictions[i]){
            //insert x
            auto y = restriction.upper_bound({x.second, numeric_limits<long long>::max()});
            if(y == restriction.begin()) {
                if(restriction.size() && y->second <= x.first){
                    //assert(y == restriction.upper_bound({x.second, numeric_limits<long long>::max()}));
                    //cout<<y->first<<","<<y->second<<","<<x.first<<","<<x.second<<endl;
                    continue;
                }
                restriction.insert({x.second, x.first});
                continue;
            }
            else y = prev(y);
            int tt = x.first;
            while(y != restriction.end() && y->first >= x.first){
                tt = min(tt, y->second);
                auto t = y;
                if(t == restriction.begin()) t= restriction.end();
                else t = prev(t);
                restriction.erase(y);
                y = t;
            }
            x.first = tt;
            while(y != restriction.end() && y->second >= x.first){
                assert(false);
            }
            auto z = restriction.upper_bound(x);
            //if(z != restriction.end() && z->second <= x.first) continue;
            restriction.insert({x.second, x.first});
        }
    }
    auto x = restriction.begin();
    while(x != restriction.end()){
        if(x != restriction.begin()){
            assert(x->first > prev(x)->first);
            assert(x->second > prev(x)->second);
        }
        x = next(x);
    }
    set<pair<int,int>> bruh;
    for(auto &x : restriction) bruh.insert({x.second, x.first});
    restriction=bruh;
    return;
}

long long arrival_time(long long Y)
{
    auto yes = upper_bound(restriction.begin(), restriction.end(), make_pair( Y, numeric_limits<long long>::max() ));
    if(yes == restriction.begin()) yes = restriction.end();
    else yes = prev(yes);
    if (yes != restriction.end()) Y = max(Y, yes->second);
    return Y + x * l;
}

Compilation message (stderr)

overtaking.cpp: In function 'void init(int32_t, int32_t, std::vector<long long int>, std::vector<int>, int32_t, int32_t, std::vector<int>)':
overtaking.cpp:37:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for(int j = 1; j < restrictions[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~~~
overtaking.cpp:75:18: warning: variable 'z' set but not used [-Wunused-but-set-variable]
   75 |             auto z = restriction.upper_bound(x);
      |                  ^

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 26
• Subtask 5: 0 / 35