Submission #858593

#	Time	Username	Problem	Language	Result	Execution time	Memory
858593		resting	Overtaking (IOI23_overtaking)	C++17	19 / 100	14 ms	1300 KiB

overtaking

#include <bits/stdc++.h>

using namespace std;
#define int long long

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

int x, l;
bool comp(const pair<int,int>&a, const pair<int,int>&b){
    if(a.second == b.second) return a.first > b.first;
    return a.second < b.second;
}
vector<pair<int,int>> fix(vector<pair<int,int>> shit){
    vector<pair<int,int>> res;
    sort(shit.begin(), shit.end());
    for(int i = shit.size()-1; i >= 0; i--){
        if(res.size() && shit[i].first >= res.back().first) continue;
        res.push_back(shit[i]);
    }
    reverse(res.begin(), res.end());
    return res;
}
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)
{
    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].first + cur[j].second * (S[i + 1] - S[i]), cur[j].second });
        for (int j = 0; j < T - 1; j++) if (res[j].first > res[j + 1].first) res[j + 1].first = res[j].first;
        int p  = -1;
        for (int j = 0; j < T; j++) {
            if(res[j].first != p){
                if(j + 1 == T || cur[j].first != cur[j+1].first){
                    p = res[j].first;
                    restrictions[i].push_back({ cur[j].first+1, res[j].first }); //start, end
                }
            }
        }

        //for(int j = 0; j < restrictions[i].size(); j++) cout<<restrictions[i][j].first<<","<<restrictions[i][j].second<<endl;
        //cout<<endl;
        swap(res, cur);
    }
    //restrictions i guess ["start after i has to end after j"]
    restriction = restrictions[0];
    //    cout<<"restriction"<<endl;
   // for(auto &x : restriction) cout<<x.first<<" "<<x.second<<endl;
    for (int i = 1; i < M; i++) {
        //transition from prev ???
        //two pointers
        vector<pair<int, int>> nice;
        auto l1 = restriction, l2 = restrictions[i];
        l1 = fix(l1);
        l2 = fix(l2);
        int p1 = l1.size() - 1;
        int p2 = l2.size() - 1;
        int cur = numeric_limits<long long>::max();
        while (p1 >= 0 || p2 >= 0) {
          //  cout<<"A: "<<p1<<","<<p2<<endl;
            if (p1 < 0) {
                nice.push_back(l2[p2]);
                cur = l2[p2].first;
                p2--;
            } else if (p2 < 0) {
                nice.push_back(l1[p1]);
                cur = l1[p1].first;
                p1--;
            } else if (l1[p1].second < l2[p2].second) {
                int a = l2[p2].first;
                while (l1[p1].second >= l2[p2].first) {
                    a = min(a, l1[p1].first);
                    p1--;
                } 
                l2[p2].first = a;
                nice.push_back(l2[p2]);
                cur = l2[p2].first;
                p2--;
            } else {
                assert(l1[p1].second >= l2[p2].second);
                nice.push_back(l1[p1]);
                cur = l1[p1].first;
                p1--;
            }
            while (p1 >= 0 && l1[p1].first >= cur) p1--;
            while (p2 >= 0 && l2[p2].first >= cur) p2--;
        }
        swap(restriction, nice);
        restriction = fix(restriction);
        //reverse(restriction.begin(), restriction.end());
       // cout<<"restriction"<<endl;
  //  for(auto &x : restriction) cout<<x.first<<" "<<x.second<<endl;
    }


    return;
}

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

Compilation message (stderr)

overtaking.cpp: In function 'long long int arrival_time(long long int)':
overtaking.cpp:106:25: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     if (yes >= 0 && yes <= restriction.size()) Y = max(Y, restriction[yes].second);
      |                     ~~~~^~~~~~~~~~~~~~~~~~~~~

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