# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
420574 | 2021-06-08T12:47:50 Z | Nicholas_Patrick | Autobahn (COI21_autobahn) | C++17 | 149 ms | 19952 KB |
#include <cstdio> #include <queue> #include <algorithm> using namespace std; struct person{ int l, r, t; }; struct event{ int type, time; /* 0: count++ 1: count-- 2: pay++ 3: pay-- 4: do nothing */ event(int a, int b):type(a), time(b){} bool operator<(event rhs)const{ return time<rhs.time; } }; int main(){ int n, k, x; scanf("%d%d%d", &n, &k, &x); vector<person> people(n); vector<event> events; for(auto& i : people){ scanf("%d%d%d", &i.l, &i.t, &i.r), i.l--; i.t+=i.l; events.emplace_back(0, i.l); events.emplace_back(1, i.r); events.emplace_back(4, i.l+x); events.emplace_back(4, i.r-x); if(i.t<i.r){ events.emplace_back(2, i.t); events.emplace_back(3, i.r); events.emplace_back(4, i.t+x); } } vector<long long> prefixhappy{0}; sort(events.begin(), events.end()); int lastTime=events[0].time; int count=0, pay=0; for(auto i : events){ prefixhappy.push_back(prefixhappy.back()+(long long)(count>=k)*pay*(i.time-lastTime)); lastTime=i.time; if(i.type==0) count++; if(i.type==1) count--; if(i.type==2) pay++; if(i.type==3) pay--; } long long ans=0; for(int i=1, j=0; i<prefixhappy.size(); i++){ while(j+1<prefixhappy.size() and events[j-1].time+x<events[i-1].time) j++; ans=max(ans, prefixhappy[i]-prefixhappy[j]); } printf("%lld\n", ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Correct | 1 ms | 204 KB | Output is correct |
5 | Correct | 1 ms | 204 KB | Output is correct |
6 | Correct | 1 ms | 204 KB | Output is correct |
7 | Correct | 0 ms | 204 KB | Output is correct |
8 | Correct | 0 ms | 204 KB | Output is correct |
9 | Correct | 0 ms | 204 KB | Output is correct |
10 | Correct | 0 ms | 204 KB | Output is correct |
11 | Correct | 0 ms | 204 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Correct | 1 ms | 204 KB | Output is correct |
5 | Correct | 1 ms | 204 KB | Output is correct |
6 | Correct | 1 ms | 204 KB | Output is correct |
7 | Correct | 0 ms | 204 KB | Output is correct |
8 | Correct | 0 ms | 204 KB | Output is correct |
9 | Correct | 0 ms | 204 KB | Output is correct |
10 | Correct | 0 ms | 204 KB | Output is correct |
11 | Correct | 0 ms | 204 KB | Output is correct |
12 | Correct | 1 ms | 408 KB | Output is correct |
13 | Correct | 1 ms | 460 KB | Output is correct |
14 | Correct | 1 ms | 460 KB | Output is correct |
15 | Correct | 1 ms | 460 KB | Output is correct |
16 | Correct | 2 ms | 460 KB | Output is correct |
17 | Correct | 1 ms | 460 KB | Output is correct |
18 | Correct | 1 ms | 460 KB | Output is correct |
19 | Correct | 1 ms | 416 KB | Output is correct |
20 | Correct | 1 ms | 460 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Correct | 1 ms | 204 KB | Output is correct |
5 | Correct | 1 ms | 204 KB | Output is correct |
6 | Correct | 1 ms | 204 KB | Output is correct |
7 | Correct | 0 ms | 204 KB | Output is correct |
8 | Correct | 0 ms | 204 KB | Output is correct |
9 | Correct | 0 ms | 204 KB | Output is correct |
10 | Correct | 0 ms | 204 KB | Output is correct |
11 | Correct | 0 ms | 204 KB | Output is correct |
12 | Correct | 1 ms | 408 KB | Output is correct |
13 | Correct | 1 ms | 460 KB | Output is correct |
14 | Correct | 1 ms | 460 KB | Output is correct |
15 | Correct | 1 ms | 460 KB | Output is correct |
16 | Correct | 2 ms | 460 KB | Output is correct |
17 | Correct | 1 ms | 460 KB | Output is correct |
18 | Correct | 1 ms | 460 KB | Output is correct |
19 | Correct | 1 ms | 416 KB | Output is correct |
20 | Correct | 1 ms | 460 KB | Output is correct |
21 | Correct | 132 ms | 19700 KB | Output is correct |
22 | Correct | 149 ms | 19796 KB | Output is correct |
23 | Correct | 132 ms | 19768 KB | Output is correct |
24 | Correct | 130 ms | 19744 KB | Output is correct |
25 | Correct | 131 ms | 19824 KB | Output is correct |
26 | Correct | 128 ms | 19952 KB | Output is correct |
27 | Correct | 128 ms | 19768 KB | Output is correct |
28 | Correct | 126 ms | 19872 KB | Output is correct |
29 | Correct | 128 ms | 19760 KB | Output is correct |