QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#526573#8775. MountainCraftlsflsf2023#WA 1ms8100kbC++142.3kb2024-08-21 17:54:392024-08-21 17:54:39

Judging History

你现在查看的是最新测评结果

  • [2024-08-21 17:54:39]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:8100kb
  • [2024-08-21 17:54:39]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

pair < int , int > Q[200005];

bool Opt[200005];

map < pair < int , int > , int > Map;

int LL[400005];

int Pos[400005];

int a[200005];

int B[200005];
int C[200005];
int Sum[500], RR[500], Top[500], L[500], R[500];

int main()
{
	int q, w;
	scanf("%d%d", &q, &w);
	int t = 0;
	for (int i = 1 ; i <= q ; ++ i)
	  {
	  	int x, y;
	  	scanf("%d%d", &x, &y);
	  	if (Map[make_pair(x, y)] == 0)
	  	  Opt[i] = 1, Map[make_pair(x, y)] = 1;
	  	else
	  	  Opt[i] = 0, Map[make_pair(x, y)] = 0;
	  	int l = x - y;
	  	if (l < 0)
	  	  l = 0;
	  	int r = x + y;
	  	if (r > w)
	  	  r = w;
        Q[i].first = l, Q[i].second = r;
        LL[++ t] = l, LL[++ t] = r;
	  }
	sort(LL + 1, LL + t + 1);
	int n = 0;
	map < int , int > M;
	for (int i = 1 ; i <= t ; ++ i)
	  if (!M[LL[i]])
	    M[LL[i]] = ++ n, Pos[n] = LL[i];
	for (int i = 1 ; i <= q ; ++ i)
	  Q[i].first = M[Q[i].first], Q[i].second = M[Q[i].second] - 1;
	for (int i = 1 ; i < n ; ++ i)
	  a[i] = Pos[i + 1] - Pos[i];
	-- n;
	int S = sqrt(n);
	for (int i = 1 ; i <= n ; ++ i)
	  B[i] = (i - 1) / S + 1, Top[B[i]] += a[i], RR[B[i]] = i;
	for (int i = n ; i ; -- i)
	  L[B[i]] = i;
	int Ans = 0;
	for (int i = 1 ; i <= q ; ++ i)
	  {
	  	int l = Q[i].first, r = Q[i].second;
	  	if (Opt[i] == 1)
	  	  {
	  	  	for (int j = B[l] + 1 ; j < B[r] ; ++ j)
	  	  	  {
	  	  	  	++ Sum[j];
	  	  	  	Ans += Top[j] - R[j];
			  }
			for (int j = l ; j <= RR[l] ; ++ j)
			  {
			  	++ C[j];
			  	if (Sum[j] == 0 && C[j] == 1)
			  	  R[j] += a[j], Ans += a[j];
			  }
			for (int j = L[r] ; j <= r ; ++ j)
			  {
			  	++ C[j];
			  	if (Sum[j] == 0 && C[j] == 1)
			  	  R[j] += a[j], Ans += a[j];
			  }
		  }
		else
		  {
		  	for (int j = B[l] + 1 ; j < B[r] ; ++ j)
		  	  {
		  	  	-- Sum[j];
		  	  	if (Sum[j] == 0)
		  	  	  Ans -= Top[j] - R[j];
			  }
			for (int j = l ; j <= RR[l] ; ++ j)
			  {
			  	-- C[j];
			  	if (Sum[j] == 0 && C[j] == 0)
			  	  R[j] -= a[j], Ans -= a[j];
			  }
			for (int j = L[r] ; j <= r ; ++ j)
			  {
			  	-- C[j];
			  	if (Sum[j] == 0 && C[j] == 0)
			  	  R[j] -= a[j], Ans -= a[j];
			  }
		  }
		printf("%.6lf\n", (double)Ans * sqrt(2));
	  }
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 8100kb

input:

3 10
3 2
7 3
9 6

output:

5.656854
12.727922
12.727922

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 1ms
memory: 7944kb

input:

5 100
31 41
59 26
31 41
59 26
31 41

output:

101.823376
120.208153
73.539105
0.000000
101.823376

result:

ok 5 numbers

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 7964kb

input:

100 10
6 4
2 3
7 6
5 5
3 6
7 5
5 8
10 4
9 8
0 9
9 10
9 3
2 3
10 10
8 4
10 9
0 1
1 7
0 2
3 4
10 3
3 10
7 4
7 5
1 4
0 7
1 9
5 6
8 8
7 4
8 1
3 9
2 1
5 5
2 1
10 9
8 4
0 9
10 7
4 1
9 10
8 6
5 4
1 4
0 9
9 3
4 8
5 10
7 2
8 10
7 10
3 4
2 2
8 5
0 9
5 3
1 4
6 4
0 3
8 1
1 6
3 8
8 4
6 5
10 2
2 2
8 4
6 1
2 4
6 4...

output:

19.798990
19.798990
28.284271
36.769553
41.012193
49.497475
57.982756
57.982756
66.468037
70.710678
79.195959
79.195959
79.195959
87.681241
91.923882
100.409163
100.409163
104.651804
104.651804
108.894444
108.894444
117.379726
121.622366
121.622366
121.622366
125.865007
134.350288
142.835570
151.320...

result:

wrong answer 1st numbers differ - expected: '11.3137085', found: '19.7989900', error = '0.7500000'