#include <bits/stdc++.h>
using namespace std;
int seg[1 << 19];
int lazy[1 << 19];
int lb[1 << 19];
int rb[1 << 19];
void build(int c, int l, int r){
lb[c] = l;
rb[c] = r;
seg[c] = 0;
if(l == r) return;
int k = (l+r)/2;
build(2*c, l, k);
build(2*c+1, k+1, r);
}
inline void prop(int c){
seg[c] += lazy[c];
if(lb[c] != rb[c]){
lazy[2*c] += lazy[c];
lazy[2*c+1] += lazy[c];
}
lazy[c] = 0;
}
void update(int c, int l, int r, int x = 1){
if(lb[c] == l && rb[c] == r) lazy[c] += x;
prop(c);
if(lb[c] == l && rb[c] == r) return;
int k = (lb[c] + rb[c])/2;
if(l <= k && k < r){
update(2*c, l, k, x);
update(2*c+1, k+1, r, x);
}else if(r <= k){
update(2*c, l, r, x);
prop(2*c+1);
}else{
prop(2*c);
update(2*c+1, l, r, x);
}
seg[c] = max(seg[2*c], seg[2*c+1]);
}
int query(int c, int l, int r){
prop(c);
if(lb[c] == l && rb[c] == r) return seg[c];
int k = (lb[c] + rb[c])/2;
if(l <= k && k < r) return max(query(2*c, l, k), query(2*c+1, k+1, r));
else if(r <= k) return query(2*c, l, r);
else return query(2*c+1, l, r);
}
int main(){
int n, m;
scanf("%d%d",&n,&m);
vector<tuple<int,int,int> > dat;
for(int i = 0; i < m; i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(a > b) swap(a, b);
b--;
dat.emplace_back(a,b,c);
}
sort(dat.begin(), dat.end(), [](tuple<int,int,int> x, tuple<int,int,int> y){
return get<1>(x) - get<0>(x) > get<1>(y) - get<0>(y);
});
int lo = 1;
int hi = m;
int mid;
while(lo < hi){
mid = (lo + hi)/2;
build(1, 1, n);
for(auto d : dat){
update(1, get<0>(d), get<1>(d));
}
bool ok = query(1, 1, n) <= mid;
if(!ok)
for(auto d : dat){
if(query(1, get<0>(d), get<1>(d)) > mid){
update(1, 1, n, 1);
update(1, get<0>(d), get<1>(d), -2);
}
if(query(1, 1, n) <= mid){
ok = true;
break;
}
}
if(ok){
hi = mid;
}else{
lo = mid+1;
}
}
printf("%d\n", lo);
return 0;
}
Compilation message
arranging_tickets.cpp: In function 'int main()':
arranging_tickets.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
52 | scanf("%d%d",&n,&m);
| ~~~~~^~~~~~~~~~~~~~
arranging_tickets.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
56 | scanf("%d%d%d",&a,&b,&c);
| ~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
