#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
using namespace std;
using pii = pair<int, int>;
const int MAXN = 2e5+2, MAXM = 1e5+2;
int n, m;
int a[MAXM], b[MAXM], c[MAXM];
int cnt[MAXN], sweep[MAXN];
int pref[MAXN], suf[MAXN];
bool flip[MAXM];
priority_queue<pair<pii, int>> pq;
const int base = (1<<18);
int tree_l[2*base+1], tree_r[2*base+1], push_l[2*base+1], push_r[2*base+1];
void upd(int id, int val, int (&tree)[2*base+1], int (&push)[2*base+1]) {
tree[id] += val;
push[id] += val;
}
void ins(int l, int r, int val, int (&tree)[2*base+1], int (&push)[2*base+1], int id=1, int rl=0, int rr=base-1) {
if(l > rr || r < rl) return;
if(l<=rl && r>=rr) {
upd(id, val, tree, push);
return;
}
upd(id*2, push[id], tree, push), upd(id*2+1, push[id], tree, push);
push[id] = 0;
ins(l, r, val, tree, push, id*2, rl, (rl+rr)/2), ins(l, r, val, tree, push, id*2+1, (rl+rr)/2+1, rr);
tree[id] = min(tree[id*2], tree[id*2+1]);
}
int qry(int l, int r, int (&tree)[2*base+1], int (&push)[2*base+1], int id=1, int rl=0, int rr=base-1) {
if(l > rr || r < rl) return m;
if(l<=rl && r>=rr) {
return tree[id];
}
upd(id*2, push[id], tree, push), upd(id*2+1, push[id], tree, push);
push[id] = 0;
return min(qry(l, r, tree, push, id*2, rl, (rl+rr)/2), qry(l, r, tree, push, id*2+1, (rl+rr)/2+1, rr));
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n>>m;
for(int i=0; i<m; ++i) {
cin>>a[i]>>b[i]>>c[i];
if(a[i] > b[i]) {
swap(a[i], b[i]);
}
b[i]--;
sweep[a[i]]++;
sweep[b[i]+1]--;
pq.push(mp(mp(b[i], a[i]), i));
}
int cur_sum = 0, max_sum = 0;
for(int i=1; i<=n; ++i) {
cur_sum += sweep[i];
sweep[i] = 0;
cnt[i] = cur_sum;
max_sum = max(max_sum, cnt[i]);
}
for(int i=1; i<2*base; ++i) {
tree_l[i] = tree_r[i] = (max_sum)/2;
}
for(int i=1; i<=n; ++i) {
if(cnt[i] == max_sum) tree_l[i+base] = 0;
else tree_l[i+base] = min(tree_l[i-1+base], (max_sum - cnt[i])/2);
}
for(int i=n; i>=1; --i) {
if(cnt[i] == max_sum) tree_r[i+base] = 0;
else tree_r[i+base] = min(tree_r[i+1+base], (max_sum - cnt[i])/2);
}
for(int i=base-1; i>=1; --i) {
tree_l[i] = min(tree_l[i*2], tree_l[i*2+1]);
tree_r[i] = min(tree_r[i*2], tree_r[i*2+1]);
}
int ans = max_sum;
while(pq.size()) {
auto cur = pq.top();
swap(cur.st.st, cur.st.nd);
pq.pop();
if(qry(0, cur.st.st-1, tree_l, push_l) > 0 && qry(cur.st.nd+1, n+1, tree_r, push_r) > 0) {
flip[cur.nd] = 1;
ans--;
ins(0, cur.st.st-1, -1, tree_l, push_l);
ins(cur.st.nd+1, n+1, -1, tree_r, push_r);
}
}
for(int i=0; i<m; ++i) {
if(!flip[i]) {
sweep[a[i]]++;
sweep[b[i]+1]--;
}
else {
sweep[b[i]+1]++;
sweep[n+1]--;
sweep[1]++;
sweep[a[i]]--;
}
}
cur_sum = 0;
max_sum = 0;
for(int i=1; i<=n; ++i) {
cur_sum += sweep[i];
sweep[i] = 0;
cnt[i] = cur_sum;
max_sum = max(max_sum, cnt[i]);
}
int l = n+1, r = 0;
for(int i=1; i<=n; ++i) {
if(cnt[i] == max_sum) {
l = min(l, i);
r = i;
}
}
int cand1=-1, cand2=-1;
for(int i=0; i<m; ++i) {
if(!flip[i] && a[i] <= l && b[i] >= r) {
if(cand1==-1 || a[i] < a[cand1]) {
cand1 = i;
}
if(cand2==-1 || b[i] > b[cand2]) {
cand2 = i;
}
}
}
if(cand1!=-1 && cand2!=-1 && cand1 != cand2) {
max_sum = 0;
for(int i=1; i<a[cand1]; ++i) {
max_sum = max(max_sum, cnt[i]+2);
}
for(int i=b[cand2]+1; i<=n; ++i) {
max_sum = max(max_sum, cnt[i]+2);
}
if(max_sum < ans) {
ans--;
}
}
cout<<ans<<'\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4588 KB |
Output is correct |
2 |
Correct |
4 ms |
4588 KB |
Output is correct |
3 |
Correct |
4 ms |
4588 KB |
Output is correct |
4 |
Correct |
4 ms |
4588 KB |
Output is correct |
5 |
Correct |
4 ms |
4588 KB |
Output is correct |
6 |
Correct |
6 ms |
4588 KB |
Output is correct |
7 |
Correct |
4 ms |
4588 KB |
Output is correct |
8 |
Correct |
4 ms |
4588 KB |
Output is correct |
9 |
Correct |
4 ms |
4588 KB |
Output is correct |
10 |
Correct |
4 ms |
4588 KB |
Output is correct |
11 |
Correct |
4 ms |
4588 KB |
Output is correct |
12 |
Correct |
4 ms |
4588 KB |
Output is correct |
13 |
Correct |
4 ms |
4588 KB |
Output is correct |
14 |
Correct |
4 ms |
4588 KB |
Output is correct |
15 |
Correct |
5 ms |
4588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4588 KB |
Output is correct |
2 |
Correct |
4 ms |
4588 KB |
Output is correct |
3 |
Correct |
4 ms |
4588 KB |
Output is correct |
4 |
Correct |
4 ms |
4588 KB |
Output is correct |
5 |
Correct |
4 ms |
4588 KB |
Output is correct |
6 |
Correct |
6 ms |
4588 KB |
Output is correct |
7 |
Correct |
4 ms |
4588 KB |
Output is correct |
8 |
Correct |
4 ms |
4588 KB |
Output is correct |
9 |
Correct |
4 ms |
4588 KB |
Output is correct |
10 |
Correct |
4 ms |
4588 KB |
Output is correct |
11 |
Correct |
4 ms |
4588 KB |
Output is correct |
12 |
Correct |
4 ms |
4588 KB |
Output is correct |
13 |
Correct |
4 ms |
4588 KB |
Output is correct |
14 |
Correct |
4 ms |
4588 KB |
Output is correct |
15 |
Correct |
5 ms |
4588 KB |
Output is correct |
16 |
Correct |
5 ms |
4588 KB |
Output is correct |
17 |
Correct |
4 ms |
4588 KB |
Output is correct |
18 |
Correct |
4 ms |
4588 KB |
Output is correct |
19 |
Correct |
4 ms |
4588 KB |
Output is correct |
20 |
Correct |
4 ms |
4588 KB |
Output is correct |
21 |
Correct |
5 ms |
4588 KB |
Output is correct |
22 |
Correct |
4 ms |
4588 KB |
Output is correct |
23 |
Correct |
5 ms |
4588 KB |
Output is correct |
24 |
Correct |
4 ms |
4588 KB |
Output is correct |
25 |
Correct |
4 ms |
4588 KB |
Output is correct |
26 |
Correct |
5 ms |
4588 KB |
Output is correct |
27 |
Correct |
5 ms |
4588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4588 KB |
Output is correct |
2 |
Correct |
4 ms |
4588 KB |
Output is correct |
3 |
Correct |
4 ms |
4588 KB |
Output is correct |
4 |
Correct |
4 ms |
4588 KB |
Output is correct |
5 |
Correct |
4 ms |
4588 KB |
Output is correct |
6 |
Correct |
6 ms |
4588 KB |
Output is correct |
7 |
Correct |
4 ms |
4588 KB |
Output is correct |
8 |
Correct |
4 ms |
4588 KB |
Output is correct |
9 |
Correct |
4 ms |
4588 KB |
Output is correct |
10 |
Correct |
4 ms |
4588 KB |
Output is correct |
11 |
Correct |
4 ms |
4588 KB |
Output is correct |
12 |
Correct |
4 ms |
4588 KB |
Output is correct |
13 |
Correct |
4 ms |
4588 KB |
Output is correct |
14 |
Correct |
4 ms |
4588 KB |
Output is correct |
15 |
Correct |
5 ms |
4588 KB |
Output is correct |
16 |
Correct |
5 ms |
4588 KB |
Output is correct |
17 |
Correct |
4 ms |
4588 KB |
Output is correct |
18 |
Correct |
4 ms |
4588 KB |
Output is correct |
19 |
Correct |
4 ms |
4588 KB |
Output is correct |
20 |
Correct |
4 ms |
4588 KB |
Output is correct |
21 |
Correct |
5 ms |
4588 KB |
Output is correct |
22 |
Correct |
4 ms |
4588 KB |
Output is correct |
23 |
Correct |
5 ms |
4588 KB |
Output is correct |
24 |
Correct |
4 ms |
4588 KB |
Output is correct |
25 |
Correct |
4 ms |
4588 KB |
Output is correct |
26 |
Correct |
5 ms |
4588 KB |
Output is correct |
27 |
Correct |
5 ms |
4588 KB |
Output is correct |
28 |
Correct |
8 ms |
4844 KB |
Output is correct |
29 |
Correct |
9 ms |
4844 KB |
Output is correct |
30 |
Correct |
8 ms |
4844 KB |
Output is correct |
31 |
Correct |
8 ms |
4844 KB |
Output is correct |
32 |
Correct |
9 ms |
4844 KB |
Output is correct |
33 |
Correct |
8 ms |
4844 KB |
Output is correct |
34 |
Correct |
8 ms |
4716 KB |
Output is correct |
35 |
Correct |
9 ms |
4832 KB |
Output is correct |
36 |
Correct |
8 ms |
4716 KB |
Output is correct |
37 |
Correct |
10 ms |
4716 KB |
Output is correct |
38 |
Correct |
6 ms |
4716 KB |
Output is correct |
39 |
Correct |
7 ms |
4716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4588 KB |
Output is correct |
2 |
Correct |
4 ms |
4588 KB |
Output is correct |
3 |
Correct |
4 ms |
4588 KB |
Output is correct |
4 |
Correct |
4 ms |
4588 KB |
Output is correct |
5 |
Correct |
4 ms |
4588 KB |
Output is correct |
6 |
Correct |
6 ms |
4588 KB |
Output is correct |
7 |
Correct |
4 ms |
4588 KB |
Output is correct |
8 |
Correct |
4 ms |
4588 KB |
Output is correct |
9 |
Correct |
4 ms |
4588 KB |
Output is correct |
10 |
Correct |
4 ms |
4588 KB |
Output is correct |
11 |
Correct |
4 ms |
4588 KB |
Output is correct |
12 |
Correct |
4 ms |
4588 KB |
Output is correct |
13 |
Correct |
4 ms |
4588 KB |
Output is correct |
14 |
Correct |
4 ms |
4588 KB |
Output is correct |
15 |
Correct |
5 ms |
4588 KB |
Output is correct |
16 |
Correct |
5 ms |
4588 KB |
Output is correct |
17 |
Correct |
4 ms |
4588 KB |
Output is correct |
18 |
Correct |
4 ms |
4588 KB |
Output is correct |
19 |
Correct |
4 ms |
4588 KB |
Output is correct |
20 |
Correct |
4 ms |
4588 KB |
Output is correct |
21 |
Correct |
5 ms |
4588 KB |
Output is correct |
22 |
Correct |
4 ms |
4588 KB |
Output is correct |
23 |
Correct |
5 ms |
4588 KB |
Output is correct |
24 |
Correct |
4 ms |
4588 KB |
Output is correct |
25 |
Correct |
4 ms |
4588 KB |
Output is correct |
26 |
Correct |
5 ms |
4588 KB |
Output is correct |
27 |
Correct |
5 ms |
4588 KB |
Output is correct |
28 |
Correct |
8 ms |
4844 KB |
Output is correct |
29 |
Correct |
9 ms |
4844 KB |
Output is correct |
30 |
Correct |
8 ms |
4844 KB |
Output is correct |
31 |
Correct |
8 ms |
4844 KB |
Output is correct |
32 |
Correct |
9 ms |
4844 KB |
Output is correct |
33 |
Correct |
8 ms |
4844 KB |
Output is correct |
34 |
Correct |
8 ms |
4716 KB |
Output is correct |
35 |
Correct |
9 ms |
4832 KB |
Output is correct |
36 |
Correct |
8 ms |
4716 KB |
Output is correct |
37 |
Correct |
10 ms |
4716 KB |
Output is correct |
38 |
Correct |
6 ms |
4716 KB |
Output is correct |
39 |
Correct |
7 ms |
4716 KB |
Output is correct |
40 |
Correct |
175 ms |
12392 KB |
Output is correct |
41 |
Correct |
192 ms |
12276 KB |
Output is correct |
42 |
Correct |
176 ms |
12256 KB |
Output is correct |
43 |
Correct |
204 ms |
13152 KB |
Output is correct |
44 |
Correct |
179 ms |
13280 KB |
Output is correct |
45 |
Correct |
203 ms |
13152 KB |
Output is correct |
46 |
Correct |
166 ms |
11744 KB |
Output is correct |
47 |
Correct |
193 ms |
11744 KB |
Output is correct |
48 |
Correct |
165 ms |
11996 KB |
Output is correct |
49 |
Correct |
145 ms |
10080 KB |
Output is correct |
50 |
Correct |
96 ms |
10080 KB |
Output is correct |
51 |
Correct |
149 ms |
10080 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4588 KB |
Output is correct |
2 |
Correct |
4 ms |
4588 KB |
Output is correct |
3 |
Correct |
4 ms |
4588 KB |
Output is correct |
4 |
Correct |
4 ms |
4588 KB |
Output is correct |
5 |
Correct |
4 ms |
4588 KB |
Output is correct |
6 |
Correct |
6 ms |
4588 KB |
Output is correct |
7 |
Correct |
4 ms |
4588 KB |
Output is correct |
8 |
Correct |
4 ms |
4588 KB |
Output is correct |
9 |
Correct |
4 ms |
4588 KB |
Output is correct |
10 |
Correct |
4 ms |
4588 KB |
Output is correct |
11 |
Correct |
4 ms |
4588 KB |
Output is correct |
12 |
Correct |
4 ms |
4588 KB |
Output is correct |
13 |
Correct |
4 ms |
4588 KB |
Output is correct |
14 |
Correct |
4 ms |
4588 KB |
Output is correct |
15 |
Correct |
5 ms |
4588 KB |
Output is correct |
16 |
Correct |
5 ms |
4588 KB |
Output is correct |
17 |
Correct |
4 ms |
4588 KB |
Output is correct |
18 |
Correct |
4 ms |
4588 KB |
Output is correct |
19 |
Correct |
4 ms |
4588 KB |
Output is correct |
20 |
Correct |
4 ms |
4588 KB |
Output is correct |
21 |
Correct |
5 ms |
4588 KB |
Output is correct |
22 |
Correct |
4 ms |
4588 KB |
Output is correct |
23 |
Correct |
5 ms |
4588 KB |
Output is correct |
24 |
Correct |
4 ms |
4588 KB |
Output is correct |
25 |
Correct |
4 ms |
4588 KB |
Output is correct |
26 |
Correct |
5 ms |
4588 KB |
Output is correct |
27 |
Correct |
5 ms |
4588 KB |
Output is correct |
28 |
Correct |
8 ms |
4844 KB |
Output is correct |
29 |
Correct |
9 ms |
4844 KB |
Output is correct |
30 |
Correct |
8 ms |
4844 KB |
Output is correct |
31 |
Correct |
8 ms |
4844 KB |
Output is correct |
32 |
Correct |
9 ms |
4844 KB |
Output is correct |
33 |
Correct |
8 ms |
4844 KB |
Output is correct |
34 |
Correct |
8 ms |
4716 KB |
Output is correct |
35 |
Correct |
9 ms |
4832 KB |
Output is correct |
36 |
Correct |
8 ms |
4716 KB |
Output is correct |
37 |
Correct |
10 ms |
4716 KB |
Output is correct |
38 |
Correct |
6 ms |
4716 KB |
Output is correct |
39 |
Correct |
7 ms |
4716 KB |
Output is correct |
40 |
Correct |
175 ms |
12392 KB |
Output is correct |
41 |
Correct |
192 ms |
12276 KB |
Output is correct |
42 |
Correct |
176 ms |
12256 KB |
Output is correct |
43 |
Correct |
204 ms |
13152 KB |
Output is correct |
44 |
Correct |
179 ms |
13280 KB |
Output is correct |
45 |
Correct |
203 ms |
13152 KB |
Output is correct |
46 |
Correct |
166 ms |
11744 KB |
Output is correct |
47 |
Correct |
193 ms |
11744 KB |
Output is correct |
48 |
Correct |
165 ms |
11996 KB |
Output is correct |
49 |
Correct |
145 ms |
10080 KB |
Output is correct |
50 |
Correct |
96 ms |
10080 KB |
Output is correct |
51 |
Correct |
149 ms |
10080 KB |
Output is correct |
52 |
Incorrect |
187 ms |
12896 KB |
Output isn't correct |
53 |
Halted |
0 ms |
0 KB |
- |