#include "bits/stdc++.h"
using namespace std;
#define ar array
#define int long long
const int N = 2e5 + 5;
struct ST{
int tree[N << 2], P[N << 2];
void flush(){
memset(tree, 0, sizeof tree);
memset(P, 0, sizeof P);
}
void push(int x, int lx, int rx){
if(lx == rx) return;
tree[x<<1] += P[x], P[x<<1] += P[x];
tree[x<<1|1] += P[x], P[x<<1|1] += P[x];
P[x] = 0;
}
void add(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
if(lx > r || rx < l) return;
if(lx >= l && rx <= r){
tree[x] += v, P[x] += v;
return;
} int m = (lx + rx) >> 1;
push(x, lx, rx);
add(l, r, v, lx, m, x<<1),
add(l, r, v, m+1, rx, x<<1|1);
tree[x] = max(tree[x<<1], tree[x<<1|1]);
}
int get(int l, int r, int lx = 0, int rx = N, int x = 1){
if(lx > r || rx < l) return 0;
if(lx >= l && rx <= r) return tree[x];
int m = (lx + rx) >> 1;
push(x, lx, rx);
return max(get(l, r, lx, m, x<<1), get(l, r, m+1, rx, x<<1|1));
}
}tree;
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n, m; cin>>n>>m;
vector<int> l(n), r(n), c(n);
for(int i=0;i<m;i++){
cin>>l[i]>>r[i]>>c[i];
if(l[i] > r[i]) swap(l[i], r[i]);
r[i]--;
}
auto check = [&](int mx){
vector<ar<int, 2>> tt;
tree.flush();
for(int i=0;i<m;i++){
tt.push_back({l[i], i + 1});
tt.push_back({r[i] + 1, -i - 1});
tree.add(l[i], r[i], 1);
}
bool ans = false;
vector<int> used(m), is(m);
for(int i=0, j=0;i<(int)tt.size();){
while(j < (int)tt.size() && tt[j][0] == tt[i][0]){
int in = abs(tt[j][1]) - 1;
if(tt[j][1] > 0) used[in] = 1;
else used[in] = 0;
tree.add(l[in], r[in], (used[in] ? -1 : 1));
j++;
}
vector<int> p;
for(int k=0;k<m;k++){
if(used[k]) p.push_back(k);
}
sort(p.begin(), p.end(), [&](int i, int j){
if(l[i] != l[j]) return l[i] < l[j];
return r[i] > r[j];
});
for(auto j : p){
if(tree.get(0, l[j] - 1) < mx && tree.get(r[j] + 1, n) < mx){
is[j] = 1;
tree.add(0, l[j] - 1, 1);
tree.add(r[j] + 1, n, 1);
} else tree.add(l[j], r[j], 1);
}
if(tree.get(0, N) <= mx) { ans = true; break; }
//~ for(int i=1;i<=n;i++) cout<<tree.get(i, i)<<" ";
//~ cout<<"\n";
for(auto j : p){
if(is[j]){
is[j] = 0;
tree.add(0, l[j] - 1, -1);
tree.add(r[j] + 1, n, -1);
} else tree.add(l[j], r[j], -1);
}
i = j;
}
return ans;
};
int lx = 1, rx = m * 1e9;
while(lx < rx){
int m = (lx + rx) >> 1;
if(check(m)) rx = m;
else lx = m + 1;
}
cout<<lx<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
12756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
12756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
12756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
12756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
12756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
