Submission #671747

#	Time	Username	Problem	Language	Result	Execution time	Memory
671747		Username4132	Autobahn (COI21_autobahn)	C++14	100 / 100	213 ms	10724 KiB

autobahn

#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
using pii = pair<int, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)

const int MAXN = 1e5+10;
int n, k, x, cn;
int in1[MAXN], in2[MAXN], in3[MAXN], impt[2*MAXN], lv[MAXN], rv[MAXN];
long long pl[MAXN], pr[MAXN];
pii segs[MAXN];
multiset<int> rs;
vector<int> trs, keys;
vector<long long> segsum;

long long find_sum(int x){
    long long lcnt = upper_bound(lv, lv+cn, x) - lv;
    long long rcnt = upper_bound(rv, rv+cn, x) - rv;
    return (lcnt-rcnt)*x + pr[rcnt] - pl[lcnt];
}

long long true_sum(int x){
    int pos = lower_bound(trs.begin(), trs.end(), x) - trs.begin();
    if(pos&1) return segsum[pos>>1] + find_sum(x) - find_sum(trs[pos-1]);
    else return segsum[pos>>1];
}

int main(){
    cin >> n >> k >> x;
    forn(i, n) cin >> in1[i] >> in2[i] >> in3[i], impt[i]=in1[i], impt[n+i]=in3[i]+1, segs[i] = {in1[i], in3[i]+1};
    forn(i, n) if(in1[i]+in2[i]<=in3[i]) lv[cn]=in1[i]+in2[i], rv[cn++]=in3[i]+1;

    sort(segs, segs+n);
    sort(impt, impt+2*n);
    sort(lv, lv+cn);
    sort(rv, rv+cn);
    forn(i, cn) pl[i+1] = pl[i]+lv[i], pr[i+1] = pr[i]+rv[i];

    bool flag=false;
    int cur=0;
    forn(i, 2*n){
        while(cur<n && segs[cur].first<=impt[i]) rs.insert(segs[cur++].second);
        while(!rs.empty() && *rs.begin()<=impt[i]) rs.erase(rs.begin());
        if(flag==true ^ rs.size()>=k){
            trs.push_back(impt[i]);
            flag^=1;
        }
    }

    segsum.assign((trs.size()>>1) +1, 0);
    for(int i=0; i<trs.size(); i+=2){
        segsum[(i>>1) + 1] = find_sum(trs[i+1]) - find_sum(trs[i]) + segsum[i>>1];
    }

    forn(i, trs.size()>>1){
        keys.push_back(trs[i<<1]);
        keys.push_back(trs[i<<1|1]-x);
    }
    forn(i, cn){
        keys.push_back(lv[i]);
        keys.push_back(rv[i]-x);
    }

    long long mx=0;
    for(auto el:keys){
        mx = max(mx, true_sum(el+x) - true_sum(el));
    }

    cout << mx << '\n';
}

Compilation message (stderr)

autobahn.cpp: In function 'int main()':
autobahn.cpp:46:34: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |         if(flag==true ^ rs.size()>=k){
      |                         ~~~~~~~~~^~~
autobahn.cpp:46:16: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   46 |         if(flag==true ^ rs.size()>=k){
      |            ~~~~^~~~~~
autobahn.cpp:53:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i=0; i<trs.size(); i+=2){
      |                  ~^~~~~~~~~~~

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