#include <bits/stdc++.h>
using namespace std;
int stree[1<<20];
int lazy[1<<20];
int treeN;
void ul(int n)
{
stree[n]+=lazy[n];
if(n<treeN)
{
lazy[n*2]+=lazy[n];
lazy[n*2+1]+=lazy[n];
}
lazy[n]=0;
}
void upd(int qs,int qe,int p,int s=0,int e=treeN-1,int i=1)
{
ul(i);
if(s>qe||qs>e)
return;
if(qs<=s&&e<=qe)
{
lazy[i]+=p;
ul(i);
return;
}
upd(qs,qe,p,s,(s+e)/2,i*2);
upd(qs,qe,p,(s+e)/2+1,e,i*2+1);
stree[i]=max(stree[i*2],stree[i*2+1]);
}
int arr[100100][2];
bool v[100100];
int main()
{
int N,M;
cin >>N>>M;
for(treeN=1;treeN<N;treeN*=2);
int i;
for(i=0;i<M;i++)
{
int a;
cin >>arr[i][0]>>arr[i][1]>>a;
if(arr[i][0]>arr[i][1])
swap(arr[i][0],arr[i][1]);
arr[i][1]--;
upd(arr[i][0],arr[i][1],1);
}
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<int> d(0,M-1);
int T=1000000;
int mi=1<<30;
while(T--)
{
int a=d(gen);
int b=stree[1];
if(v[a])
{
upd(arr[a][0],arr[a][1],2);
upd(0,N-1,-1);
}
else
{
upd(arr[a][0],arr[a][1],-2);
upd(0,N-1,1);
}
v[a]=1-v[a];
mi=min(mi,b);
if(stree[1]>b)
{
if(d(gen)==0)
continue;
if(v[a])
{
upd(arr[a][0],arr[a][1],2);
upd(0,N-1,-1);
}
else
{
upd(arr[a][0],arr[a][1],-2);
upd(0,N-1,1);
}
v[a]=1-v[a];
}
}
cout <<mi;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
375 ms |
312 KB |
Output is correct |
2 |
Correct |
409 ms |
308 KB |
Output is correct |
3 |
Correct |
350 ms |
212 KB |
Output is correct |
4 |
Correct |
367 ms |
312 KB |
Output is correct |
5 |
Correct |
337 ms |
308 KB |
Output is correct |
6 |
Correct |
348 ms |
308 KB |
Output is correct |
7 |
Correct |
373 ms |
308 KB |
Output is correct |
8 |
Correct |
352 ms |
308 KB |
Output is correct |
9 |
Correct |
346 ms |
332 KB |
Output is correct |
10 |
Correct |
371 ms |
308 KB |
Output is correct |
11 |
Correct |
365 ms |
308 KB |
Output is correct |
12 |
Correct |
377 ms |
308 KB |
Output is correct |
13 |
Correct |
403 ms |
308 KB |
Output is correct |
14 |
Correct |
373 ms |
308 KB |
Output is correct |
15 |
Correct |
341 ms |
308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
375 ms |
312 KB |
Output is correct |
2 |
Correct |
409 ms |
308 KB |
Output is correct |
3 |
Correct |
350 ms |
212 KB |
Output is correct |
4 |
Correct |
367 ms |
312 KB |
Output is correct |
5 |
Correct |
337 ms |
308 KB |
Output is correct |
6 |
Correct |
348 ms |
308 KB |
Output is correct |
7 |
Correct |
373 ms |
308 KB |
Output is correct |
8 |
Correct |
352 ms |
308 KB |
Output is correct |
9 |
Correct |
346 ms |
332 KB |
Output is correct |
10 |
Correct |
371 ms |
308 KB |
Output is correct |
11 |
Correct |
365 ms |
308 KB |
Output is correct |
12 |
Correct |
377 ms |
308 KB |
Output is correct |
13 |
Correct |
403 ms |
308 KB |
Output is correct |
14 |
Correct |
373 ms |
308 KB |
Output is correct |
15 |
Correct |
341 ms |
308 KB |
Output is correct |
16 |
Correct |
797 ms |
320 KB |
Output is correct |
17 |
Correct |
863 ms |
320 KB |
Output is correct |
18 |
Correct |
838 ms |
340 KB |
Output is correct |
19 |
Correct |
828 ms |
332 KB |
Output is correct |
20 |
Correct |
864 ms |
340 KB |
Output is correct |
21 |
Correct |
805 ms |
320 KB |
Output is correct |
22 |
Correct |
849 ms |
340 KB |
Output is correct |
23 |
Correct |
832 ms |
340 KB |
Output is correct |
24 |
Correct |
808 ms |
340 KB |
Output is correct |
25 |
Correct |
742 ms |
316 KB |
Output is correct |
26 |
Correct |
786 ms |
320 KB |
Output is correct |
27 |
Correct |
804 ms |
320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
375 ms |
312 KB |
Output is correct |
2 |
Correct |
409 ms |
308 KB |
Output is correct |
3 |
Correct |
350 ms |
212 KB |
Output is correct |
4 |
Correct |
367 ms |
312 KB |
Output is correct |
5 |
Correct |
337 ms |
308 KB |
Output is correct |
6 |
Correct |
348 ms |
308 KB |
Output is correct |
7 |
Correct |
373 ms |
308 KB |
Output is correct |
8 |
Correct |
352 ms |
308 KB |
Output is correct |
9 |
Correct |
346 ms |
332 KB |
Output is correct |
10 |
Correct |
371 ms |
308 KB |
Output is correct |
11 |
Correct |
365 ms |
308 KB |
Output is correct |
12 |
Correct |
377 ms |
308 KB |
Output is correct |
13 |
Correct |
403 ms |
308 KB |
Output is correct |
14 |
Correct |
373 ms |
308 KB |
Output is correct |
15 |
Correct |
341 ms |
308 KB |
Output is correct |
16 |
Correct |
797 ms |
320 KB |
Output is correct |
17 |
Correct |
863 ms |
320 KB |
Output is correct |
18 |
Correct |
838 ms |
340 KB |
Output is correct |
19 |
Correct |
828 ms |
332 KB |
Output is correct |
20 |
Correct |
864 ms |
340 KB |
Output is correct |
21 |
Correct |
805 ms |
320 KB |
Output is correct |
22 |
Correct |
849 ms |
340 KB |
Output is correct |
23 |
Correct |
832 ms |
340 KB |
Output is correct |
24 |
Correct |
808 ms |
340 KB |
Output is correct |
25 |
Correct |
742 ms |
316 KB |
Output is correct |
26 |
Correct |
786 ms |
320 KB |
Output is correct |
27 |
Correct |
804 ms |
320 KB |
Output is correct |
28 |
Correct |
1210 ms |
388 KB |
Output is correct |
29 |
Correct |
1274 ms |
396 KB |
Output is correct |
30 |
Correct |
1402 ms |
396 KB |
Output is correct |
31 |
Correct |
1321 ms |
396 KB |
Output is correct |
32 |
Correct |
1533 ms |
392 KB |
Output is correct |
33 |
Incorrect |
1403 ms |
388 KB |
Output isn't correct |
34 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
375 ms |
312 KB |
Output is correct |
2 |
Correct |
409 ms |
308 KB |
Output is correct |
3 |
Correct |
350 ms |
212 KB |
Output is correct |
4 |
Correct |
367 ms |
312 KB |
Output is correct |
5 |
Correct |
337 ms |
308 KB |
Output is correct |
6 |
Correct |
348 ms |
308 KB |
Output is correct |
7 |
Correct |
373 ms |
308 KB |
Output is correct |
8 |
Correct |
352 ms |
308 KB |
Output is correct |
9 |
Correct |
346 ms |
332 KB |
Output is correct |
10 |
Correct |
371 ms |
308 KB |
Output is correct |
11 |
Correct |
365 ms |
308 KB |
Output is correct |
12 |
Correct |
377 ms |
308 KB |
Output is correct |
13 |
Correct |
403 ms |
308 KB |
Output is correct |
14 |
Correct |
373 ms |
308 KB |
Output is correct |
15 |
Correct |
341 ms |
308 KB |
Output is correct |
16 |
Correct |
797 ms |
320 KB |
Output is correct |
17 |
Correct |
863 ms |
320 KB |
Output is correct |
18 |
Correct |
838 ms |
340 KB |
Output is correct |
19 |
Correct |
828 ms |
332 KB |
Output is correct |
20 |
Correct |
864 ms |
340 KB |
Output is correct |
21 |
Correct |
805 ms |
320 KB |
Output is correct |
22 |
Correct |
849 ms |
340 KB |
Output is correct |
23 |
Correct |
832 ms |
340 KB |
Output is correct |
24 |
Correct |
808 ms |
340 KB |
Output is correct |
25 |
Correct |
742 ms |
316 KB |
Output is correct |
26 |
Correct |
786 ms |
320 KB |
Output is correct |
27 |
Correct |
804 ms |
320 KB |
Output is correct |
28 |
Correct |
1210 ms |
388 KB |
Output is correct |
29 |
Correct |
1274 ms |
396 KB |
Output is correct |
30 |
Correct |
1402 ms |
396 KB |
Output is correct |
31 |
Correct |
1321 ms |
396 KB |
Output is correct |
32 |
Correct |
1533 ms |
392 KB |
Output is correct |
33 |
Incorrect |
1403 ms |
388 KB |
Output isn't correct |
34 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
375 ms |
312 KB |
Output is correct |
2 |
Correct |
409 ms |
308 KB |
Output is correct |
3 |
Correct |
350 ms |
212 KB |
Output is correct |
4 |
Correct |
367 ms |
312 KB |
Output is correct |
5 |
Correct |
337 ms |
308 KB |
Output is correct |
6 |
Correct |
348 ms |
308 KB |
Output is correct |
7 |
Correct |
373 ms |
308 KB |
Output is correct |
8 |
Correct |
352 ms |
308 KB |
Output is correct |
9 |
Correct |
346 ms |
332 KB |
Output is correct |
10 |
Correct |
371 ms |
308 KB |
Output is correct |
11 |
Correct |
365 ms |
308 KB |
Output is correct |
12 |
Correct |
377 ms |
308 KB |
Output is correct |
13 |
Correct |
403 ms |
308 KB |
Output is correct |
14 |
Correct |
373 ms |
308 KB |
Output is correct |
15 |
Correct |
341 ms |
308 KB |
Output is correct |
16 |
Correct |
797 ms |
320 KB |
Output is correct |
17 |
Correct |
863 ms |
320 KB |
Output is correct |
18 |
Correct |
838 ms |
340 KB |
Output is correct |
19 |
Correct |
828 ms |
332 KB |
Output is correct |
20 |
Correct |
864 ms |
340 KB |
Output is correct |
21 |
Correct |
805 ms |
320 KB |
Output is correct |
22 |
Correct |
849 ms |
340 KB |
Output is correct |
23 |
Correct |
832 ms |
340 KB |
Output is correct |
24 |
Correct |
808 ms |
340 KB |
Output is correct |
25 |
Correct |
742 ms |
316 KB |
Output is correct |
26 |
Correct |
786 ms |
320 KB |
Output is correct |
27 |
Correct |
804 ms |
320 KB |
Output is correct |
28 |
Correct |
1210 ms |
388 KB |
Output is correct |
29 |
Correct |
1274 ms |
396 KB |
Output is correct |
30 |
Correct |
1402 ms |
396 KB |
Output is correct |
31 |
Correct |
1321 ms |
396 KB |
Output is correct |
32 |
Correct |
1533 ms |
392 KB |
Output is correct |
33 |
Incorrect |
1403 ms |
388 KB |
Output isn't correct |
34 |
Halted |
0 ms |
0 KB |
- |