#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;
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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1120 ms |
308 KB |
Output is correct |
2 |
Correct |
1245 ms |
300 KB |
Output is correct |
3 |
Correct |
1100 ms |
308 KB |
Output is correct |
4 |
Correct |
1193 ms |
304 KB |
Output is correct |
5 |
Correct |
1195 ms |
312 KB |
Output is correct |
6 |
Correct |
1190 ms |
308 KB |
Output is correct |
7 |
Correct |
1237 ms |
308 KB |
Output is correct |
8 |
Correct |
1185 ms |
308 KB |
Output is correct |
9 |
Correct |
1183 ms |
312 KB |
Output is correct |
10 |
Correct |
1187 ms |
308 KB |
Output is correct |
11 |
Correct |
1166 ms |
308 KB |
Output is correct |
12 |
Correct |
1307 ms |
308 KB |
Output is correct |
13 |
Correct |
1133 ms |
312 KB |
Output is correct |
14 |
Correct |
1153 ms |
312 KB |
Output is correct |
15 |
Correct |
1065 ms |
308 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1120 ms |
308 KB |
Output is correct |
2 |
Correct |
1245 ms |
300 KB |
Output is correct |
3 |
Correct |
1100 ms |
308 KB |
Output is correct |
4 |
Correct |
1193 ms |
304 KB |
Output is correct |
5 |
Correct |
1195 ms |
312 KB |
Output is correct |
6 |
Correct |
1190 ms |
308 KB |
Output is correct |
7 |
Correct |
1237 ms |
308 KB |
Output is correct |
8 |
Correct |
1185 ms |
308 KB |
Output is correct |
9 |
Correct |
1183 ms |
312 KB |
Output is correct |
10 |
Correct |
1187 ms |
308 KB |
Output is correct |
11 |
Correct |
1166 ms |
308 KB |
Output is correct |
12 |
Correct |
1307 ms |
308 KB |
Output is correct |
13 |
Correct |
1133 ms |
312 KB |
Output is correct |
14 |
Correct |
1153 ms |
312 KB |
Output is correct |
15 |
Correct |
1065 ms |
308 KB |
Output is correct |
16 |
Correct |
2507 ms |
320 KB |
Output is correct |
17 |
Correct |
2667 ms |
320 KB |
Output is correct |
18 |
Correct |
2851 ms |
320 KB |
Output is correct |
19 |
Correct |
2506 ms |
320 KB |
Output is correct |
20 |
Correct |
2654 ms |
320 KB |
Output is correct |
21 |
Correct |
2564 ms |
340 KB |
Output is correct |
22 |
Correct |
2667 ms |
320 KB |
Output is correct |
23 |
Correct |
2670 ms |
320 KB |
Output is correct |
24 |
Correct |
2689 ms |
320 KB |
Output is correct |
25 |
Correct |
2370 ms |
320 KB |
Output is correct |
26 |
Correct |
2719 ms |
324 KB |
Output is correct |
27 |
Correct |
2362 ms |
320 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1120 ms |
308 KB |
Output is correct |
2 |
Correct |
1245 ms |
300 KB |
Output is correct |
3 |
Correct |
1100 ms |
308 KB |
Output is correct |
4 |
Correct |
1193 ms |
304 KB |
Output is correct |
5 |
Correct |
1195 ms |
312 KB |
Output is correct |
6 |
Correct |
1190 ms |
308 KB |
Output is correct |
7 |
Correct |
1237 ms |
308 KB |
Output is correct |
8 |
Correct |
1185 ms |
308 KB |
Output is correct |
9 |
Correct |
1183 ms |
312 KB |
Output is correct |
10 |
Correct |
1187 ms |
308 KB |
Output is correct |
11 |
Correct |
1166 ms |
308 KB |
Output is correct |
12 |
Correct |
1307 ms |
308 KB |
Output is correct |
13 |
Correct |
1133 ms |
312 KB |
Output is correct |
14 |
Correct |
1153 ms |
312 KB |
Output is correct |
15 |
Correct |
1065 ms |
308 KB |
Output is correct |
16 |
Correct |
2507 ms |
320 KB |
Output is correct |
17 |
Correct |
2667 ms |
320 KB |
Output is correct |
18 |
Correct |
2851 ms |
320 KB |
Output is correct |
19 |
Correct |
2506 ms |
320 KB |
Output is correct |
20 |
Correct |
2654 ms |
320 KB |
Output is correct |
21 |
Correct |
2564 ms |
340 KB |
Output is correct |
22 |
Correct |
2667 ms |
320 KB |
Output is correct |
23 |
Correct |
2670 ms |
320 KB |
Output is correct |
24 |
Correct |
2689 ms |
320 KB |
Output is correct |
25 |
Correct |
2370 ms |
320 KB |
Output is correct |
26 |
Correct |
2719 ms |
324 KB |
Output is correct |
27 |
Correct |
2362 ms |
320 KB |
Output is correct |
28 |
Correct |
3464 ms |
396 KB |
Output is correct |
29 |
Correct |
3497 ms |
396 KB |
Output is correct |
30 |
Correct |
3612 ms |
392 KB |
Output is correct |
31 |
Correct |
3413 ms |
392 KB |
Output is correct |
32 |
Correct |
3359 ms |
392 KB |
Output is correct |
33 |
Incorrect |
3503 ms |
392 KB |
Output isn't correct |
34 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1120 ms |
308 KB |
Output is correct |
2 |
Correct |
1245 ms |
300 KB |
Output is correct |
3 |
Correct |
1100 ms |
308 KB |
Output is correct |
4 |
Correct |
1193 ms |
304 KB |
Output is correct |
5 |
Correct |
1195 ms |
312 KB |
Output is correct |
6 |
Correct |
1190 ms |
308 KB |
Output is correct |
7 |
Correct |
1237 ms |
308 KB |
Output is correct |
8 |
Correct |
1185 ms |
308 KB |
Output is correct |
9 |
Correct |
1183 ms |
312 KB |
Output is correct |
10 |
Correct |
1187 ms |
308 KB |
Output is correct |
11 |
Correct |
1166 ms |
308 KB |
Output is correct |
12 |
Correct |
1307 ms |
308 KB |
Output is correct |
13 |
Correct |
1133 ms |
312 KB |
Output is correct |
14 |
Correct |
1153 ms |
312 KB |
Output is correct |
15 |
Correct |
1065 ms |
308 KB |
Output is correct |
16 |
Correct |
2507 ms |
320 KB |
Output is correct |
17 |
Correct |
2667 ms |
320 KB |
Output is correct |
18 |
Correct |
2851 ms |
320 KB |
Output is correct |
19 |
Correct |
2506 ms |
320 KB |
Output is correct |
20 |
Correct |
2654 ms |
320 KB |
Output is correct |
21 |
Correct |
2564 ms |
340 KB |
Output is correct |
22 |
Correct |
2667 ms |
320 KB |
Output is correct |
23 |
Correct |
2670 ms |
320 KB |
Output is correct |
24 |
Correct |
2689 ms |
320 KB |
Output is correct |
25 |
Correct |
2370 ms |
320 KB |
Output is correct |
26 |
Correct |
2719 ms |
324 KB |
Output is correct |
27 |
Correct |
2362 ms |
320 KB |
Output is correct |
28 |
Correct |
3464 ms |
396 KB |
Output is correct |
29 |
Correct |
3497 ms |
396 KB |
Output is correct |
30 |
Correct |
3612 ms |
392 KB |
Output is correct |
31 |
Correct |
3413 ms |
392 KB |
Output is correct |
32 |
Correct |
3359 ms |
392 KB |
Output is correct |
33 |
Incorrect |
3503 ms |
392 KB |
Output isn't correct |
34 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1120 ms |
308 KB |
Output is correct |
2 |
Correct |
1245 ms |
300 KB |
Output is correct |
3 |
Correct |
1100 ms |
308 KB |
Output is correct |
4 |
Correct |
1193 ms |
304 KB |
Output is correct |
5 |
Correct |
1195 ms |
312 KB |
Output is correct |
6 |
Correct |
1190 ms |
308 KB |
Output is correct |
7 |
Correct |
1237 ms |
308 KB |
Output is correct |
8 |
Correct |
1185 ms |
308 KB |
Output is correct |
9 |
Correct |
1183 ms |
312 KB |
Output is correct |
10 |
Correct |
1187 ms |
308 KB |
Output is correct |
11 |
Correct |
1166 ms |
308 KB |
Output is correct |
12 |
Correct |
1307 ms |
308 KB |
Output is correct |
13 |
Correct |
1133 ms |
312 KB |
Output is correct |
14 |
Correct |
1153 ms |
312 KB |
Output is correct |
15 |
Correct |
1065 ms |
308 KB |
Output is correct |
16 |
Correct |
2507 ms |
320 KB |
Output is correct |
17 |
Correct |
2667 ms |
320 KB |
Output is correct |
18 |
Correct |
2851 ms |
320 KB |
Output is correct |
19 |
Correct |
2506 ms |
320 KB |
Output is correct |
20 |
Correct |
2654 ms |
320 KB |
Output is correct |
21 |
Correct |
2564 ms |
340 KB |
Output is correct |
22 |
Correct |
2667 ms |
320 KB |
Output is correct |
23 |
Correct |
2670 ms |
320 KB |
Output is correct |
24 |
Correct |
2689 ms |
320 KB |
Output is correct |
25 |
Correct |
2370 ms |
320 KB |
Output is correct |
26 |
Correct |
2719 ms |
324 KB |
Output is correct |
27 |
Correct |
2362 ms |
320 KB |
Output is correct |
28 |
Correct |
3464 ms |
396 KB |
Output is correct |
29 |
Correct |
3497 ms |
396 KB |
Output is correct |
30 |
Correct |
3612 ms |
392 KB |
Output is correct |
31 |
Correct |
3413 ms |
392 KB |
Output is correct |
32 |
Correct |
3359 ms |
392 KB |
Output is correct |
33 |
Incorrect |
3503 ms |
392 KB |
Output isn't correct |
34 |
Halted |
0 ms |
0 KB |
- |