This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct Node
{
int sum , cnt;
Node(){
sum = cnt = 0;
}
};
struct segTree
{
vector<Node> tree;
int BASE;
void build(int n)
{
BASE = n;
while(__builtin_popcount(BASE) != 1)
{
BASE++;
}
tree.assign(4*BASE , Node());
}
void upd(int node , int s , int e ,int l , int r , int val)
{
if(l > e || s > r)
return ;
if(l <= s && e <= r)
{
tree[node].cnt+=val;
}
else
{
int m = (s + e)>>1;
upd(node<<1 , s , m , l , r , val);
upd(node<<1|1 , m + 1 , e , l , r , val);
}
if(tree[node].cnt)
{
tree[node].sum = e - s + 1;
}
else
tree[node].sum = tree[node<<1].sum + tree[node<<1|1].sum;
}
void upd(int l , int r , int val)
{
if(l > r)
return;
upd(1 , 0 , BASE - 1 , l , r , val);
}
};
void run_case()
{
int n , m;
cin>>n>>m;
segTree seg;
seg.build(n);
vector<int> in[n + 1] , out[n + 1];
for(int i = 0 ; i < m ; i++)
{
int a , b , c;
cin>>a>>b>>c;
a-- , b--;
if(a > b)
swap(a , b);
in[a].push_back(b);
out[b].push_back(a);
seg.upd(a , b - 1 , 1);
}
int ans = n;
for(int i = 0 ; i <= n ; i++)
{
ans = min(ans , seg.tree[1].sum);
for(auto j : in[i])
{
seg.upd(i , j - 1, -1);
seg.upd(0 , i - 1 , 1);
seg.upd(j , n - 1 , 1);
}
for(auto j : out[i])
{
seg.upd(j , i - 1, 1);
seg.upd(0 , j - 1 , -1);
seg.upd(i , n - 1 , -1);
}
}
cout<<ans<<'\n';
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
//cin>>t;
while (t--)
{
run_case();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |