Submission #1381916
Source Code Expand
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
template<class V, int NV> struct LazySegTree { // [L,R)
vector<V> dat, lazy; LazySegTree() { dat.resize(NV * 2, def); lazy.resize(NV * 2, ldef); }
void update(int a, int b, V v, int k, int l, int r) {
push(k, l, r); if (r <= a || b <= l) return;
if (a <= l && r <= b) { setLazy(k, v); push(k, l, r); }
else {
update(a, b, v, k * 2 + 1, l, (l + r) / 2); update(a, b, v, k * 2 + 2, (l + r) / 2, r);
dat[k] = comp(dat[k * 2 + 1], dat[k * 2 + 2]);
}
}
V get(int a, int b, int k, int l, int r) {
push(k, l, r); if (r <= a || b <= l) return def;
if (a <= l && r <= b) return dat[k]; auto x = get(a, b, k * 2 + 1, l, (l + r) / 2);
auto y = get(a, b, k * 2 + 2, (l + r) / 2, r); return comp(x, y);
}
void update(int a, int b, V v) { update(a, b, v, 0, 0, NV); }
V get(int a, int b) { return get(a, b, 0, 0, NV); }
// ---- Template ---------------------------------------------------------------------------------
const V def = 0, ldef = 0;
V comp(V l, V r) { return max(l, r); }
void setLazy(int i, V v) { lazy[i] += v; }
void push(int k, int l, int r) {
if (lazy[k] != ldef) {
// modify------------------------------
dat[k] += lazy[k];
// ------------------------------------
if (r - l > 1) { setLazy(k * 2 + 1, lazy[k]); setLazy(k * 2 + 2, lazy[k]); }
lazy[k] = ldef;
}
}
};
/*---------------------------------------------------------------------------------------------------
∧_∧
∧_∧ (´<_` ) Welcome to My Coding Space!
( ´_ゝ`) / ⌒i
/ \ | |
/ / ̄ ̄ ̄ ̄/ |
__(__ニつ/ _/ .| .|____
\/____/ (u ⊃
---------------------------------------------------------------------------------------------------*/
int N, M, L[201010], R[201010];
//---------------------------------------------------------------------------------------------------
int solveO2N() { // O(2^N)
int ans = 0;
rep(mask, 1, 1 << N) {
int LL = -1, RR = M + 2, human = 0;
rep(i, 0, N) if (mask & (1 << i)) {
LL = max(LL, L[i]);
RR = min(RR, R[i]);
human++;
}
int chair = -1;
if (RR <= LL) chair = M;
else chair = LL + (M + 1 - RR);
ans = max(ans, human - chair);
}
return ans;
}
//---------------------------------------------------------------------------------------------------
int solveOM2N() { // O(M^2N)
int ans = max(0, N - M);
rep(LL, 0, M + 2) rep(RR, LL + 1, M + 2) {
int chair = LL + M + 1 - RR;
int human = 0;
rep(i, 0, N) if (L[i] <= LL && RR <= R[i]) human++;
ans = max(ans, human - chair);
}
return ans;
}
//---------------------------------------------------------------------------------------------------
pair<int, int> LR[201010];
LazySegTree<int,1<<18> st;
int solveONlogM() { // O(NlogM)
rep(i, 0, N) LR[i] = { L[i], R[i] };
sort(LR, LR + N);
rep(i, 1, M + 2) st.update(i, i + 1, i);
int ans = max(0, N - M);
rep(i, 0, N) {
st.update(0, LR[i].second + 1, 1);
// human - (LL + M + 1 - RR) = human + RR - (LL + M + 1)
ans = max(ans, st.get(0, M + 2) - (LR[i].first + M + 1));
}
return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
cin >> N >> M;
rep(i, 0, N) cin >> L[i] >> R[i];
cout << solveONlogM() << endl;
}
Submission Info
Submission Time |
|
Task |
F - Exhausted? |
User |
hamayanhamayan |
Language |
C++14 (GCC 5.4.1) |
Score |
1000 |
Code Size |
4135 Byte |
Status |
AC |
Exec Time |
174 ms |
Memory |
7552 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1000 / 1000 |
Status |
|
|
Set Name |
Test Cases |
Sample |
s1.txt, s2.txt, s3.txt, s4.txt |
All |
01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, s1.txt, s2.txt, s3.txt, s4.txt |
Case Name |
Status |
Exec Time |
Memory |
01.txt |
AC |
150 ms |
7168 KB |
02.txt |
AC |
111 ms |
6144 KB |
03.txt |
AC |
173 ms |
7552 KB |
04.txt |
AC |
171 ms |
7552 KB |
05.txt |
AC |
21 ms |
4480 KB |
06.txt |
AC |
128 ms |
6656 KB |
07.txt |
AC |
144 ms |
7552 KB |
08.txt |
AC |
174 ms |
7552 KB |
09.txt |
AC |
147 ms |
7424 KB |
10.txt |
AC |
73 ms |
5248 KB |
11.txt |
AC |
139 ms |
7552 KB |
12.txt |
AC |
115 ms |
6656 KB |
13.txt |
AC |
115 ms |
7552 KB |
14.txt |
AC |
104 ms |
7552 KB |
15.txt |
AC |
143 ms |
7552 KB |
16.txt |
AC |
83 ms |
6144 KB |
17.txt |
AC |
140 ms |
7552 KB |
18.txt |
AC |
139 ms |
7552 KB |
19.txt |
AC |
128 ms |
7168 KB |
20.txt |
AC |
138 ms |
7552 KB |
21.txt |
AC |
57 ms |
4992 KB |
22.txt |
AC |
140 ms |
7552 KB |
23.txt |
AC |
25 ms |
4864 KB |
24.txt |
AC |
140 ms |
7552 KB |
25.txt |
AC |
98 ms |
6656 KB |
26.txt |
AC |
78 ms |
6656 KB |
27.txt |
AC |
111 ms |
7296 KB |
28.txt |
AC |
103 ms |
7552 KB |
29.txt |
AC |
126 ms |
7552 KB |
30.txt |
AC |
109 ms |
7552 KB |
31.txt |
AC |
140 ms |
7552 KB |
32.txt |
AC |
126 ms |
7040 KB |
33.txt |
AC |
140 ms |
7552 KB |
34.txt |
AC |
95 ms |
6400 KB |
35.txt |
AC |
88 ms |
5888 KB |
36.txt |
AC |
140 ms |
7552 KB |
37.txt |
AC |
4 ms |
4352 KB |
38.txt |
AC |
4 ms |
4352 KB |
39.txt |
AC |
3 ms |
4352 KB |
40.txt |
AC |
4 ms |
4352 KB |
41.txt |
AC |
3 ms |
4352 KB |
42.txt |
AC |
3 ms |
4352 KB |
43.txt |
AC |
37 ms |
4352 KB |
44.txt |
AC |
4 ms |
4352 KB |
s1.txt |
AC |
3 ms |
4352 KB |
s2.txt |
AC |
4 ms |
4352 KB |
s3.txt |
AC |
4 ms |
4352 KB |
s4.txt |
AC |
4 ms |
4352 KB |