Submission #681672

#TimeUsernameProblemLanguageResultExecution timeMemory
681672qwerasdfzxclAutobahn (COI21_autobahn)C++17
100 / 100
115 ms20816 KiB
#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);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...