#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;
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<int> d(0,M-1);
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);
if(d(gen)%2)
{
v[i]=1;
upd(arr[i][0],arr[i][1],-2);
upd(0,N-1,1);
}
}
int T=3000000;
int mi=1<<30;
int c=0;
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)
{
c++;
if(d(gen)<=c/M)
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];
}
else
{
c=0;
}
}
cout <<mi;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1071 ms |
308 KB |
Output is correct |
2 |
Correct |
1172 ms |
212 KB |
Output is correct |
3 |
Correct |
1048 ms |
308 KB |
Output is correct |
4 |
Correct |
1119 ms |
312 KB |
Output is correct |
5 |
Correct |
1031 ms |
308 KB |
Output is correct |
6 |
Correct |
1032 ms |
308 KB |
Output is correct |
7 |
Correct |
1130 ms |
312 KB |
Output is correct |
8 |
Correct |
1044 ms |
312 KB |
Output is correct |
9 |
Correct |
1028 ms |
312 KB |
Output is correct |
10 |
Correct |
1105 ms |
312 KB |
Output is correct |
11 |
Correct |
1095 ms |
308 KB |
Output is correct |
12 |
Correct |
1188 ms |
308 KB |
Output is correct |
13 |
Correct |
1079 ms |
332 KB |
Output is correct |
14 |
Correct |
1097 ms |
308 KB |
Output is correct |
15 |
Correct |
1057 ms |
312 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1071 ms |
308 KB |
Output is correct |
2 |
Correct |
1172 ms |
212 KB |
Output is correct |
3 |
Correct |
1048 ms |
308 KB |
Output is correct |
4 |
Correct |
1119 ms |
312 KB |
Output is correct |
5 |
Correct |
1031 ms |
308 KB |
Output is correct |
6 |
Correct |
1032 ms |
308 KB |
Output is correct |
7 |
Correct |
1130 ms |
312 KB |
Output is correct |
8 |
Correct |
1044 ms |
312 KB |
Output is correct |
9 |
Correct |
1028 ms |
312 KB |
Output is correct |
10 |
Correct |
1105 ms |
312 KB |
Output is correct |
11 |
Correct |
1095 ms |
308 KB |
Output is correct |
12 |
Correct |
1188 ms |
308 KB |
Output is correct |
13 |
Correct |
1079 ms |
332 KB |
Output is correct |
14 |
Correct |
1097 ms |
308 KB |
Output is correct |
15 |
Correct |
1057 ms |
312 KB |
Output is correct |
16 |
Correct |
2578 ms |
340 KB |
Output is correct |
17 |
Correct |
2836 ms |
340 KB |
Output is correct |
18 |
Correct |
2963 ms |
320 KB |
Output is correct |
19 |
Correct |
2814 ms |
320 KB |
Output is correct |
20 |
Correct |
3594 ms |
320 KB |
Output is correct |
21 |
Correct |
2772 ms |
320 KB |
Output is correct |
22 |
Correct |
2603 ms |
340 KB |
Output is correct |
23 |
Correct |
2423 ms |
340 KB |
Output is correct |
24 |
Correct |
2437 ms |
340 KB |
Output is correct |
25 |
Correct |
2256 ms |
320 KB |
Output is correct |
26 |
Correct |
2448 ms |
340 KB |
Output is correct |
27 |
Correct |
2412 ms |
320 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1071 ms |
308 KB |
Output is correct |
2 |
Correct |
1172 ms |
212 KB |
Output is correct |
3 |
Correct |
1048 ms |
308 KB |
Output is correct |
4 |
Correct |
1119 ms |
312 KB |
Output is correct |
5 |
Correct |
1031 ms |
308 KB |
Output is correct |
6 |
Correct |
1032 ms |
308 KB |
Output is correct |
7 |
Correct |
1130 ms |
312 KB |
Output is correct |
8 |
Correct |
1044 ms |
312 KB |
Output is correct |
9 |
Correct |
1028 ms |
312 KB |
Output is correct |
10 |
Correct |
1105 ms |
312 KB |
Output is correct |
11 |
Correct |
1095 ms |
308 KB |
Output is correct |
12 |
Correct |
1188 ms |
308 KB |
Output is correct |
13 |
Correct |
1079 ms |
332 KB |
Output is correct |
14 |
Correct |
1097 ms |
308 KB |
Output is correct |
15 |
Correct |
1057 ms |
312 KB |
Output is correct |
16 |
Correct |
2578 ms |
340 KB |
Output is correct |
17 |
Correct |
2836 ms |
340 KB |
Output is correct |
18 |
Correct |
2963 ms |
320 KB |
Output is correct |
19 |
Correct |
2814 ms |
320 KB |
Output is correct |
20 |
Correct |
3594 ms |
320 KB |
Output is correct |
21 |
Correct |
2772 ms |
320 KB |
Output is correct |
22 |
Correct |
2603 ms |
340 KB |
Output is correct |
23 |
Correct |
2423 ms |
340 KB |
Output is correct |
24 |
Correct |
2437 ms |
340 KB |
Output is correct |
25 |
Correct |
2256 ms |
320 KB |
Output is correct |
26 |
Correct |
2448 ms |
340 KB |
Output is correct |
27 |
Correct |
2412 ms |
320 KB |
Output is correct |
28 |
Correct |
3517 ms |
396 KB |
Output is correct |
29 |
Correct |
3519 ms |
392 KB |
Output is correct |
30 |
Correct |
3604 ms |
392 KB |
Output is correct |
31 |
Correct |
3400 ms |
396 KB |
Output is correct |
32 |
Correct |
3381 ms |
396 KB |
Output is correct |
33 |
Incorrect |
3608 ms |
392 KB |
Output isn't correct |
34 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1071 ms |
308 KB |
Output is correct |
2 |
Correct |
1172 ms |
212 KB |
Output is correct |
3 |
Correct |
1048 ms |
308 KB |
Output is correct |
4 |
Correct |
1119 ms |
312 KB |
Output is correct |
5 |
Correct |
1031 ms |
308 KB |
Output is correct |
6 |
Correct |
1032 ms |
308 KB |
Output is correct |
7 |
Correct |
1130 ms |
312 KB |
Output is correct |
8 |
Correct |
1044 ms |
312 KB |
Output is correct |
9 |
Correct |
1028 ms |
312 KB |
Output is correct |
10 |
Correct |
1105 ms |
312 KB |
Output is correct |
11 |
Correct |
1095 ms |
308 KB |
Output is correct |
12 |
Correct |
1188 ms |
308 KB |
Output is correct |
13 |
Correct |
1079 ms |
332 KB |
Output is correct |
14 |
Correct |
1097 ms |
308 KB |
Output is correct |
15 |
Correct |
1057 ms |
312 KB |
Output is correct |
16 |
Correct |
2578 ms |
340 KB |
Output is correct |
17 |
Correct |
2836 ms |
340 KB |
Output is correct |
18 |
Correct |
2963 ms |
320 KB |
Output is correct |
19 |
Correct |
2814 ms |
320 KB |
Output is correct |
20 |
Correct |
3594 ms |
320 KB |
Output is correct |
21 |
Correct |
2772 ms |
320 KB |
Output is correct |
22 |
Correct |
2603 ms |
340 KB |
Output is correct |
23 |
Correct |
2423 ms |
340 KB |
Output is correct |
24 |
Correct |
2437 ms |
340 KB |
Output is correct |
25 |
Correct |
2256 ms |
320 KB |
Output is correct |
26 |
Correct |
2448 ms |
340 KB |
Output is correct |
27 |
Correct |
2412 ms |
320 KB |
Output is correct |
28 |
Correct |
3517 ms |
396 KB |
Output is correct |
29 |
Correct |
3519 ms |
392 KB |
Output is correct |
30 |
Correct |
3604 ms |
392 KB |
Output is correct |
31 |
Correct |
3400 ms |
396 KB |
Output is correct |
32 |
Correct |
3381 ms |
396 KB |
Output is correct |
33 |
Incorrect |
3608 ms |
392 KB |
Output isn't correct |
34 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1071 ms |
308 KB |
Output is correct |
2 |
Correct |
1172 ms |
212 KB |
Output is correct |
3 |
Correct |
1048 ms |
308 KB |
Output is correct |
4 |
Correct |
1119 ms |
312 KB |
Output is correct |
5 |
Correct |
1031 ms |
308 KB |
Output is correct |
6 |
Correct |
1032 ms |
308 KB |
Output is correct |
7 |
Correct |
1130 ms |
312 KB |
Output is correct |
8 |
Correct |
1044 ms |
312 KB |
Output is correct |
9 |
Correct |
1028 ms |
312 KB |
Output is correct |
10 |
Correct |
1105 ms |
312 KB |
Output is correct |
11 |
Correct |
1095 ms |
308 KB |
Output is correct |
12 |
Correct |
1188 ms |
308 KB |
Output is correct |
13 |
Correct |
1079 ms |
332 KB |
Output is correct |
14 |
Correct |
1097 ms |
308 KB |
Output is correct |
15 |
Correct |
1057 ms |
312 KB |
Output is correct |
16 |
Correct |
2578 ms |
340 KB |
Output is correct |
17 |
Correct |
2836 ms |
340 KB |
Output is correct |
18 |
Correct |
2963 ms |
320 KB |
Output is correct |
19 |
Correct |
2814 ms |
320 KB |
Output is correct |
20 |
Correct |
3594 ms |
320 KB |
Output is correct |
21 |
Correct |
2772 ms |
320 KB |
Output is correct |
22 |
Correct |
2603 ms |
340 KB |
Output is correct |
23 |
Correct |
2423 ms |
340 KB |
Output is correct |
24 |
Correct |
2437 ms |
340 KB |
Output is correct |
25 |
Correct |
2256 ms |
320 KB |
Output is correct |
26 |
Correct |
2448 ms |
340 KB |
Output is correct |
27 |
Correct |
2412 ms |
320 KB |
Output is correct |
28 |
Correct |
3517 ms |
396 KB |
Output is correct |
29 |
Correct |
3519 ms |
392 KB |
Output is correct |
30 |
Correct |
3604 ms |
392 KB |
Output is correct |
31 |
Correct |
3400 ms |
396 KB |
Output is correct |
32 |
Correct |
3381 ms |
396 KB |
Output is correct |
33 |
Incorrect |
3608 ms |
392 KB |
Output isn't correct |
34 |
Halted |
0 ms |
0 KB |
- |