AC代码
AC
相比于上一次WA，修改了这些（这没啥好多说的，idx2为-会导致一系列问题）
以及加了一个n+1（原来是n）（一般情况下不会被击穿因为如果超了我会减掉，但正巧空的默认值是0，即
xp[idx2].first）为0，正好我的判断条件是xp[idx2].first!=r，碰巧hack数据r也为0，就被击穿了，idx2没减，让我的程序WA了。
1
2
3
| for(int i=1;i<=n+1;i++) {
sumVil[i]=sumVil[i-1]+xp[i].second;
}
|
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| #include <iostream>
#include <algorithm>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll N=2e5+10,MAXP=1e11+10;
pair<ll,ll> xp[N];
ll n,m,sumVil[N];
void debug() {
for(int i=1;i<=n;i++) {
cout<<sumVil[i]<<" ";
}
cout<<endl;
for(int i=1;i<=n;i++) {
cout<<xp[i].first<<" ";
}
cout<<endl;
for(int i=1;i<=n;i++) {
cout<<xp[i].second<<" ";
}
cout<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++) {
cin>>xp[i].first;
}
for(int i=1;i<=n;i++) {
cin>>xp[i].second;
}
sort(&xp[1],&xp[n+1]);
for(int i=1;i<=n+1;i++) {
sumVil[i]=sumVil[i-1]+xp[i].second;
}
cin>>m;
for(int _=1;_<=m;_++) {
ll l,r;
cin>>l>>r;
ll idx1=lower_bound(&xp[0],&xp[n+1],make_pair(l,-MAXP))-&xp[0]-1;
ll idx2=upper_bound(&xp[0],&xp[n+1],make_pair(r, MAXP))-&xp[0];
if(idx1<0)
idx1=0;
if(xp[idx2].first!=r)
idx2--;
if(idx2<0)
idx2=0;
cout<<sumVil[idx2]-sumVil[idx1]<<endl;
}
return 0;
}
|
心路历程（WA，TLE，MLE……）
挺神奇的，就WA了一个点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include <iostream>
#include <algorithm>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll N=2e5+10,MAXP=1e11+10;
pair<ll,ll> xp[N];
ll n,m,sumVil[N];
void debug() {
for(int i=1;i<=n;i++) {
cout<<sumVil[i]<<" ";
}
cout<<endl;
for(int i=1;i<=n;i++) {
cout<<xp[i].first<<" ";
}
cout<<endl;
for(int i=1;i<=n;i++) {
cout<<xp[i].second<<" ";
}
cout<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++) {
cin>>xp[i].first;
}
for(int i=1;i<=n;i++) {
cin>>xp[i].second;
}
sort(&xp[1],&xp[n+1]);
for(int i=1;i<=n;i++) {
sumVil[i]=sumVil[i-1]+xp[i].second;
}
cin>>m;
for(int _=1;_<=m;_++) {
ll l,r;
cin>>l>>r;
ll idx1=lower_bound(&xp[0],&xp[n+1],make_pair(l,-MAXP))-&xp[0]-1;
ll idx2=upper_bound(&xp[0],&xp[n+1],make_pair(r, MAXP))-&xp[0];
if(idx1<0)
idx1=0;
if(xp[idx2].first!=r)
idx2--;
cout<<sumVil[idx2]-sumVil[idx1]<<endl;
}
return 0;
}
|