Submission #681672

#	Time	Username	Problem	Language	Result	Execution time	Memory
681672		qwerasdfzxcl	Autobahn (COI21_autobahn)	C++17	100 / 100	115 ms	20816 KiB

autobahn

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
struct Event{
    int t, typ, i; ///0 -> on, 1 -> off, 2 -> extra on, 3 -> extra off
    Event(){}
    Event(int _t, int _typ, int _i): t(_t), typ(_typ), i(_i) {}
    bool operator < (const Event &E) const{return t < E.t;}
};

struct Foo{
    int t, c;
    ll S;
    Foo(){}
    Foo(int _t): t(_t) {c = 0; S = 0;}

    bool operator < (const Foo &F) const{return t < F.t;}
};

vector<Event> E;
vector<Foo> F;
int _on1[100100], _on2[100100], cnt1, cnt2;

void on1(int x){
    assert(_on1[x]==0);
    _on1[x] = 1;
    cnt1++;
}

void off1(int x){
    assert(_on1[x]==1);
    _on1[x] = 0;
    cnt1--;
}

void on2(int x){
    assert(_on2[x]==0);
    _on2[x] = 1;
    cnt2++;
}

void off2(int x){
    assert(_on2[x]==1);
    _on2[x] = 0;
    cnt2--;
}

int main(){
    int n, k, x;
    scanf("%d %d %d", &n, &k, &x);
    for (int i=1;i<=n;i++){
        int l, t, r;
        scanf("%d %d %d", &l, &t, &r);
        E.emplace_back(l, 0, i);
        E.emplace_back(r+1, 1, i);

        if (l+t <= r){
            E.emplace_back(l+t, 2, i);
            E.emplace_back(r+1, 3, i);
        }
    }

    sort(E.begin(), E.end());
    F.emplace_back(0);
    for (int i=0;i<(int)E.size();){
        int r = i;
        while(r<(int)E.size() && E[i].t == E[r].t){
            if (E[r].typ==0) on1(E[r].i);
            else if (E[r].typ==1) off1(E[r].i);
            else if (E[r].typ==2) on2(E[r].i);
            else off2(E[r].i);
            ++r;
        }

        F.emplace_back(E[i].t);
        //printf(" t = %d: on: %d / extra: %d / k: %d\n", E[i].t, cnt1, cnt2, k);
        if (cnt1 >= k) F.back().c = cnt2;

        i = r;
    }

    for (int i=1;i<(int)F.size()-1;i++){
        F[i].S = F[i-1].S + (ll)F[i].c * (F[i+1].t - F[i].t);
    }

    //for (auto &[t, c, S]:F) printf(" %d %d %lld\n", t, c, S);

    ll ans = 0;
    for (int s=1;s<(int)F.size();s++){
        auto iter = --lower_bound(F.begin(), F.end(), Foo(F[s].t + x));

        if (iter==F.begin()) continue;
        ll val = prev(iter)->S - F[s-1].S;
        //printf("  %lld\n", val);
        val += (ll)(iter->c) * (F[s].t + x - (iter->t));
        ans = max(ans, val);

        //printf("start %d -> %lld\n", F[s].t, val);
    }

    for (int e=(int)F.size()-1;e;e--){
        auto iter = lower_bound(F.begin(), F.end(), Foo(F[e].t - x));

        if (iter==F.begin()) {ans = max(ans, F[e-1].S); continue;}
        ll val = F[e-1].S - prev(iter)->S;
        val += (ll)(prev(iter)->c) * (iter->t - (F[e].t-x));
        ans = max(ans, val);

        //printf("end %d -> %lld\n", F[e].t, val);
    }

    printf("%lld\n", ans);
    return 0;
}

Compilation message (stderr)

autobahn.cpp: In function 'int main()':
autobahn.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     scanf("%d %d %d", &n, &k, &x);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
autobahn.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         scanf("%d %d %d", &l, &t, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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