#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
using namespace std;
#define int long long
#define pb push_back
#define nl '\n'
#define fore(i, y) for(int i = 0; i < y; i++)
#define forr(i, x, y) for(int i = x;i<=y;i++)
#define forn(i, y, x) for(int i = y; i >= x; i--)
const int INF = 1e9;
int comb(int a , int b)
{
return max(a , b);
}
struct segTree
{
int BASE;
vector<int> tree;
vector<int> lazy;
void build(int n)
{
BASE = n;
while(__builtin_popcount(BASE) != 1)
BASE++;
tree.clear();
lazy.clear();
tree.assign(2*BASE , 0);
lazy.assign(2*BASE , 0);
}
void propag(int node , int x)
{
if(lazy[node] == 0)
return ;
forr(lt , 2*node , 2*node + 1)
{
lazy[lt]+=lazy[node];
tree[lt]+=lazy[node];
}
lazy[node] = 0;
}
void upd(int node , int s , int e , int l , int r , int v)
{
if(l <= s && e <= r)
{
lazy[node]+=v;
tree[node]+=v;
return ;
}
if(l > e || s > r)
return;
propag(node , (e - s + 1)/2);
int mid = (s + e)>>1;
upd(2*node , s , mid , l , r , v);
upd(2*node + 1 , mid + 1 , e , l , r , v);
tree[node] = comb(tree[2*node] , tree[2*node + 1]);
}
int query(int node , int s , int e , int l , int r)
{
if(l <= s && e <= r)
{
return tree[node];
}
if(l > e || s > r)
return 0;
propag(node , (e - s + 1)/2);
int mid = (s + e)>>1;
return comb(query(2*node , s , mid , l , r ) , query(2*node + 1 , mid + 1 , e , l , r ));
}
int query(int l ,int r)
{
if(l > r)
return 0;
return query(1 , 0 , BASE - 1 , l , r);
}
void upd(int l , int r , int v)
{
if(l > r)
return ;
upd(1 , 0 , BASE - 1 , l , r , v);
}
}tree[2];
struct Qu
{
int A , B , C;
};
int n , m;
vector<pair<int ,int>> getVals(int C , int maxIn , int maxOut)
{
return {{0 , 1} , {1 , 0}};
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int ans = INF;
cin>>n>>m;
vector<Qu> queries(m);
fore(i , m)
{
cin>>queries[i].A>>queries[i].B>>queries[i].C;
if(queries[i].A > queries[i].B)
swap(queries[i].A , queries[i].B);
}
int cnt = 40;
while(cnt--)
{
random_shuffle(queries.begin() , queries.end());
fore(i , 2)
tree[i].build(n + 1);
vector<pair<int ,int>> cur = getVals(queries[0].C , 0 ,0);
fore(i , 2)
{
tree[i].upd(queries[0].A , queries[0].B - 1, cur[i].first);
tree[i].upd(1 , queries[0].A - 1 , cur[i].second);
tree[i].upd(queries[0].B , n , cur[i].second);
}
forr(k , 1 , m - 1)
{
fore(i , 2)
{
int best[2] = {INF , INF};
int maxIn = tree[i].query(queries[k].A , queries[k].B - 1);
int maxOut = max(tree[i].query(1 , queries[k].A - 1) , tree[i].query(queries[k].B , n));
cur = getVals(queries[k].C , maxIn , maxOut);
fore(j , 2)
{
tree[i].upd(queries[k].A , queries[k].B - 1, cur[j].first);
tree[i].upd(1 , queries[k].A - 1 , cur[j].second);
tree[i].upd(queries[k].B , n , cur[j].second);
best[j] = tree[i].tree[1];
tree[i].upd(queries[k].A , queries[k].B - 1, -cur[j].first);
tree[i].upd(1 , queries[k].A - 1 , -cur[j].second);
tree[i].upd(queries[k].B , n , -cur[j].second);
}
if(best[0] < best[1])
{
int j = 0;
tree[i].upd(queries[k].A , queries[k].B - 1, cur[j].first);
tree[i].upd(1 , queries[k].A - 1 , cur[j].second);
tree[i].upd(queries[k].B , n , cur[j].second);
}
else
{
int j = 1;
tree[i].upd(queries[k].A , queries[k].B - 1, cur[j].first);
tree[i].upd(1 , queries[k].A - 1 , cur[j].second);
tree[i].upd(queries[k].B , n , cur[j].second);
}
}
}
ans = min({ans , tree[0].tree[1] , tree[1].tree[1]});
}
cout<<ans<<nl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
344 KB |
Output is correct |
2 |
Correct |
2 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
344 KB |
Output is correct |
4 |
Correct |
2 ms |
348 KB |
Output is correct |
5 |
Correct |
2 ms |
456 KB |
Output is correct |
6 |
Correct |
2 ms |
348 KB |
Output is correct |
7 |
Correct |
3 ms |
348 KB |
Output is correct |
8 |
Correct |
2 ms |
348 KB |
Output is correct |
9 |
Correct |
2 ms |
500 KB |
Output is correct |
10 |
Correct |
2 ms |
460 KB |
Output is correct |
11 |
Correct |
3 ms |
348 KB |
Output is correct |
12 |
Correct |
2 ms |
348 KB |
Output is correct |
13 |
Correct |
2 ms |
452 KB |
Output is correct |
14 |
Correct |
3 ms |
348 KB |
Output is correct |
15 |
Correct |
2 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
344 KB |
Output is correct |
2 |
Correct |
2 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
344 KB |
Output is correct |
4 |
Correct |
2 ms |
348 KB |
Output is correct |
5 |
Correct |
2 ms |
456 KB |
Output is correct |
6 |
Correct |
2 ms |
348 KB |
Output is correct |
7 |
Correct |
3 ms |
348 KB |
Output is correct |
8 |
Correct |
2 ms |
348 KB |
Output is correct |
9 |
Correct |
2 ms |
500 KB |
Output is correct |
10 |
Correct |
2 ms |
460 KB |
Output is correct |
11 |
Correct |
3 ms |
348 KB |
Output is correct |
12 |
Correct |
2 ms |
348 KB |
Output is correct |
13 |
Correct |
2 ms |
452 KB |
Output is correct |
14 |
Correct |
3 ms |
348 KB |
Output is correct |
15 |
Correct |
2 ms |
348 KB |
Output is correct |
16 |
Incorrect |
55 ms |
344 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
344 KB |
Output is correct |
2 |
Correct |
2 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
344 KB |
Output is correct |
4 |
Correct |
2 ms |
348 KB |
Output is correct |
5 |
Correct |
2 ms |
456 KB |
Output is correct |
6 |
Correct |
2 ms |
348 KB |
Output is correct |
7 |
Correct |
3 ms |
348 KB |
Output is correct |
8 |
Correct |
2 ms |
348 KB |
Output is correct |
9 |
Correct |
2 ms |
500 KB |
Output is correct |
10 |
Correct |
2 ms |
460 KB |
Output is correct |
11 |
Correct |
3 ms |
348 KB |
Output is correct |
12 |
Correct |
2 ms |
348 KB |
Output is correct |
13 |
Correct |
2 ms |
452 KB |
Output is correct |
14 |
Correct |
3 ms |
348 KB |
Output is correct |
15 |
Correct |
2 ms |
348 KB |
Output is correct |
16 |
Incorrect |
55 ms |
344 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
344 KB |
Output is correct |
2 |
Correct |
2 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
344 KB |
Output is correct |
4 |
Correct |
2 ms |
348 KB |
Output is correct |
5 |
Correct |
2 ms |
456 KB |
Output is correct |
6 |
Correct |
2 ms |
348 KB |
Output is correct |
7 |
Correct |
3 ms |
348 KB |
Output is correct |
8 |
Correct |
2 ms |
348 KB |
Output is correct |
9 |
Correct |
2 ms |
500 KB |
Output is correct |
10 |
Correct |
2 ms |
460 KB |
Output is correct |
11 |
Correct |
3 ms |
348 KB |
Output is correct |
12 |
Correct |
2 ms |
348 KB |
Output is correct |
13 |
Correct |
2 ms |
452 KB |
Output is correct |
14 |
Correct |
3 ms |
348 KB |
Output is correct |
15 |
Correct |
2 ms |
348 KB |
Output is correct |
16 |
Incorrect |
55 ms |
344 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
344 KB |
Output is correct |
2 |
Correct |
2 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
344 KB |
Output is correct |
4 |
Correct |
2 ms |
348 KB |
Output is correct |
5 |
Correct |
2 ms |
456 KB |
Output is correct |
6 |
Correct |
2 ms |
348 KB |
Output is correct |
7 |
Correct |
3 ms |
348 KB |
Output is correct |
8 |
Correct |
2 ms |
348 KB |
Output is correct |
9 |
Correct |
2 ms |
500 KB |
Output is correct |
10 |
Correct |
2 ms |
460 KB |
Output is correct |
11 |
Correct |
3 ms |
348 KB |
Output is correct |
12 |
Correct |
2 ms |
348 KB |
Output is correct |
13 |
Correct |
2 ms |
452 KB |
Output is correct |
14 |
Correct |
3 ms |
348 KB |
Output is correct |
15 |
Correct |
2 ms |
348 KB |
Output is correct |
16 |
Incorrect |
55 ms |
344 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |