#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int L, n;
cin >> L >> n;
vector<array<int, 4>> a(n);
for(int i = 0; i < n; ++i){
cin >> a[i][0] >> a[i][1] >> a[i][2];
--a[i][0], --a[i][1];
assert(a[i][2] == 1);
if(a[i][0] > a[i][1]) swap(a[i][0], a[i][1]);
}
int ans = (int)1e9;
auto sol = [&](){
vector<int> pre(L);
for(int i = 0; i < n; ++i){
if(!a[i][3]){
pre[a[i][0]] += 1;
pre[a[i][1]] -= 1;
}
else{
pre[a[i][1]] += 1;
pre[0] += 1;
pre[a[i][0]] -= 1;
}
}
int nans = 0;
for(int i = 0; i < L; ++i){
if(i) pre[i] += pre[i - 1];
nans = max(nans, pre[i]);
}
return nans;
};
assert(n <= 300);
auto doit = [&]{
for(int i = 0; i < n; ++i){
for(int j = i - 1; j < n; ++j){
for(int k = 0; k < n; ++k){
a[k][3] = (i <= k && k <= j);
}
int nans = sol();
while(true){
int now = nans;
for(int i = 0; i < n; ++i){
a[i][3] ^= 1;
int prv = now;
now = min(now, sol());
if(now == prv) a[i][3] ^= 1;
}
if(now == nans) break;
nans = now;
}
ans = min(ans, nans);
}
}
};
sort(a.begin(), a.end(), [&](array<int, 4>&x, array<int, 4>&y){return make_pair(x[1], x[0]) < make_pair(y[1], y[0]);});
doit();
sort(a.begin(), a.end(), [&](array<int, 4>&x, array<int, 4>&y){return make_pair(x[1], x[0] + x[1]) < make_pair(y[1], y[0] + y[1]);});
doit();
sort(a.begin(), a.end(), [&](array<int, 4>&x, array<int, 4>&y){return make_pair(x[1], x[0] - x[1]) < make_pair(y[1], y[0] - y[1]);});
doit();
sort(a.begin(), a.end(), [&](array<int, 4>&x, array<int, 4>&y){return make_pair(x[0], x[1]) < make_pair(y[0], y[1]);});
doit();
sort(a.begin(), a.end(), [&](array<int, 4>&x, array<int, 4>&y){return make_pair(x[0], x[0] + x[1]) < make_pair(y[0], y[0] + y[1]);});
doit();
sort(a.begin(), a.end(), [&](array<int, 4>&x, array<int, 4>&y){return make_pair(x[0], x[0] - x[1]) < make_pair(y[0], y[0] - y[1]);});
doit();
sort(a.begin(), a.end(), [&](array<int, 4>&x, array<int, 4>&y){return x[0] + x[1] < y[0] + y[1];});
doit();
sort(a.begin(), a.end(), [&](array<int, 4>&x, array<int, 4>&y){return x[0] < y[0];});
doit();
sort(a.begin(), a.end(), [&](array<int, 4>&x, array<int, 4>&y){return x[0] - x[1] < y[0] - y[1];});
doit();
sort(a.begin(), a.end(), [&](array<int, 4>&x, array<int, 4>&y){return x[1] < y[1];});
doit();
cout << ans << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
212 KB |
Output is correct |
2 |
Correct |
8 ms |
212 KB |
Output is correct |
3 |
Correct |
9 ms |
232 KB |
Output is correct |
4 |
Correct |
8 ms |
212 KB |
Output is correct |
5 |
Correct |
8 ms |
308 KB |
Output is correct |
6 |
Correct |
8 ms |
212 KB |
Output is correct |
7 |
Correct |
8 ms |
212 KB |
Output is correct |
8 |
Correct |
8 ms |
212 KB |
Output is correct |
9 |
Correct |
8 ms |
320 KB |
Output is correct |
10 |
Correct |
8 ms |
212 KB |
Output is correct |
11 |
Correct |
8 ms |
212 KB |
Output is correct |
12 |
Correct |
8 ms |
316 KB |
Output is correct |
13 |
Correct |
8 ms |
316 KB |
Output is correct |
14 |
Correct |
8 ms |
212 KB |
Output is correct |
15 |
Correct |
8 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
212 KB |
Output is correct |
2 |
Correct |
8 ms |
212 KB |
Output is correct |
3 |
Correct |
9 ms |
232 KB |
Output is correct |
4 |
Correct |
8 ms |
212 KB |
Output is correct |
5 |
Correct |
8 ms |
308 KB |
Output is correct |
6 |
Correct |
8 ms |
212 KB |
Output is correct |
7 |
Correct |
8 ms |
212 KB |
Output is correct |
8 |
Correct |
8 ms |
212 KB |
Output is correct |
9 |
Correct |
8 ms |
320 KB |
Output is correct |
10 |
Correct |
8 ms |
212 KB |
Output is correct |
11 |
Correct |
8 ms |
212 KB |
Output is correct |
12 |
Correct |
8 ms |
316 KB |
Output is correct |
13 |
Correct |
8 ms |
316 KB |
Output is correct |
14 |
Correct |
8 ms |
212 KB |
Output is correct |
15 |
Correct |
8 ms |
212 KB |
Output is correct |
16 |
Execution timed out |
6071 ms |
212 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
212 KB |
Output is correct |
2 |
Correct |
8 ms |
212 KB |
Output is correct |
3 |
Correct |
9 ms |
232 KB |
Output is correct |
4 |
Correct |
8 ms |
212 KB |
Output is correct |
5 |
Correct |
8 ms |
308 KB |
Output is correct |
6 |
Correct |
8 ms |
212 KB |
Output is correct |
7 |
Correct |
8 ms |
212 KB |
Output is correct |
8 |
Correct |
8 ms |
212 KB |
Output is correct |
9 |
Correct |
8 ms |
320 KB |
Output is correct |
10 |
Correct |
8 ms |
212 KB |
Output is correct |
11 |
Correct |
8 ms |
212 KB |
Output is correct |
12 |
Correct |
8 ms |
316 KB |
Output is correct |
13 |
Correct |
8 ms |
316 KB |
Output is correct |
14 |
Correct |
8 ms |
212 KB |
Output is correct |
15 |
Correct |
8 ms |
212 KB |
Output is correct |
16 |
Execution timed out |
6071 ms |
212 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
212 KB |
Output is correct |
2 |
Correct |
8 ms |
212 KB |
Output is correct |
3 |
Correct |
9 ms |
232 KB |
Output is correct |
4 |
Correct |
8 ms |
212 KB |
Output is correct |
5 |
Correct |
8 ms |
308 KB |
Output is correct |
6 |
Correct |
8 ms |
212 KB |
Output is correct |
7 |
Correct |
8 ms |
212 KB |
Output is correct |
8 |
Correct |
8 ms |
212 KB |
Output is correct |
9 |
Correct |
8 ms |
320 KB |
Output is correct |
10 |
Correct |
8 ms |
212 KB |
Output is correct |
11 |
Correct |
8 ms |
212 KB |
Output is correct |
12 |
Correct |
8 ms |
316 KB |
Output is correct |
13 |
Correct |
8 ms |
316 KB |
Output is correct |
14 |
Correct |
8 ms |
212 KB |
Output is correct |
15 |
Correct |
8 ms |
212 KB |
Output is correct |
16 |
Execution timed out |
6071 ms |
212 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
212 KB |
Output is correct |
2 |
Correct |
8 ms |
212 KB |
Output is correct |
3 |
Correct |
9 ms |
232 KB |
Output is correct |
4 |
Correct |
8 ms |
212 KB |
Output is correct |
5 |
Correct |
8 ms |
308 KB |
Output is correct |
6 |
Correct |
8 ms |
212 KB |
Output is correct |
7 |
Correct |
8 ms |
212 KB |
Output is correct |
8 |
Correct |
8 ms |
212 KB |
Output is correct |
9 |
Correct |
8 ms |
320 KB |
Output is correct |
10 |
Correct |
8 ms |
212 KB |
Output is correct |
11 |
Correct |
8 ms |
212 KB |
Output is correct |
12 |
Correct |
8 ms |
316 KB |
Output is correct |
13 |
Correct |
8 ms |
316 KB |
Output is correct |
14 |
Correct |
8 ms |
212 KB |
Output is correct |
15 |
Correct |
8 ms |
212 KB |
Output is correct |
16 |
Execution timed out |
6071 ms |
212 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |