Submission #420609

#	Time	Username	Problem	Language	Result	Execution time	Memory
420609		HappyPacMan	Autobahn (COI21_autobahn)	C++14	100 / 100	262 ms	12204 KiB

autobahn

#include <bits/stdc++.h>
using namespace std;
const int MXN = 1e5 + 5;
int N,K,X,l[MXN],t[MXN],r[MXN],prfcnt[10*MXN],prflate[10*MXN];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> K >> X;
    vector<int> coor;
    for(int i=0;i<N;i++){
        cin >> l[i] >> t[i] >> r[i];
        coor.push_back(l[i]-1); coor.push_back(l[i]); coor.push_back(l[i]+1);
        coor.push_back(l[i]+t[i]-1); coor.push_back(l[i]+t[i]); coor.push_back(l[i]+t[i]+1);
        coor.push_back(r[i]-1); coor.push_back(r[i]); coor.push_back(r[i]+1);
    }
    sort(coor.begin(),coor.end());
    coor.erase(unique(coor.begin(),coor.end()),coor.end());
    auto fnidx = [&](int u){
        return lower_bound(coor.begin(),coor.end(),u)-coor.begin();
    };
    for(int i=0;i<N;i++){
        prfcnt[fnidx(l[i])]++, prfcnt[fnidx(r[i]+1)]--;
        if(l[i]+t[i] <= r[i]) prflate[fnidx(l[i]+t[i])]++, prflate[fnidx(r[i]+1)]--;
    }
    for(int i=1;i<coor.size();i++){
        prfcnt[i] += prfcnt[i-1];
        prflate[i] += prflate[i-1];
    }
    // for(int i=0;i<coor.size();i++) cout << prfcnt[i] << ' '; cout << '\n';
    // for(int i=0;i<coor.size();i++) cout << prflate[i] << ' '; cout << '\n';
    int64_t mx = 0,cost = 0;
    for(int i=1,j=1;i<coor.size();i++){
        if(prfcnt[i] >= K) cost += (coor[i]-coor[i-1]) * 1LL * prflate[i];
        while(coor[i]-coor[j] > X){
            j++;
            if(prfcnt[j] >= K) cost -= (coor[j]-coor[j-1]) * 1LL * prflate[j];
        }
        int64_t temp = cost;
        if(prfcnt[j] >= K) temp += min(coor[j]-coor[j-1],X-(coor[i]-coor[j])) * 1LL * prflate[j];
        mx = max(mx,temp);
    }
    cost = 0;
    for(int i=1,j=1;i<coor.size()-1;i++){
        if(prfcnt[i] >= K) cost -= (coor[i]-coor[i-1]) * 1LL * prflate[i];
        while(j+1 < coor.size() && coor[j+1]-coor[i] <= X){
            j++;
            if(prfcnt[j] >= K) cost += (coor[j]-coor[j-1]) * 1LL * prflate[j];
        }
        int64_t temp = cost;
        if(prfcnt[j+1] >= K) temp += min(coor[j+1]-coor[j],X-(coor[j]-coor[i])) * 1LL * prflate[j+1];
        mx = max(mx,temp);
    }
    cout << mx << '\n';
}

Compilation message (stderr)

autobahn.cpp: In function 'int main()':
autobahn.cpp:27:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i=1;i<coor.size();i++){
      |                 ~^~~~~~~~~~~~
autobahn.cpp:34:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int i=1,j=1;i<coor.size();i++){
      |                     ~^~~~~~~~~~~~
autobahn.cpp:45:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i=1,j=1;i<coor.size()-1;i++){
      |                     ~^~~~~~~~~~~~~~
autobahn.cpp:47:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         while(j+1 < coor.size() && coor[j+1]-coor[i] <= X){
      |               ~~~~^~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50