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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
| #include <cstdio>
#include <iostream>
#include <algorithm>
#define maxN 100010
using namespace std;
struct object{ long long A, B; } f[maxN];
long long len = 0, n = 0, m = 0;
long long sum[maxN][2], ans[maxN], c[maxN];
long long last[maxN], h[maxN], p[maxN];
bool cmp (object x, object y)
{
return (x.A > y.A) || (x.A == y.A && x.B > y.B);
}
void insert (long long pos, long long x)
{
len++;
p[len] = x;
last[len] = h[pos];
h[pos] = len;
}
void change (long long x, long long posnew)
{
last[x] = h[posnew];
h[posnew] = x;
}
int Put (long long x, long long pos, long long l)
{
long long r = n;
while(l < r)
{
long long mid = (l + r) >> 1;
if(x < f[mid].A)
{
l = mid + 1;
}
else
{
r = mid;
}
}
return l;
}
long long find (long long x, long long L)
{
long long l = L, r = n;
while(l < r)
{
long long mid = (l + r + 1) >> 1;
if(sum[mid][0] - sum[L - 1][0] > x)
{
r = mid - 1;
}
else
{
l = mid;
}
}
return l;
}
int main ()
{
scanf("%lld %lld", &n, &m);
for(long long i = 1;i <= n; i++)
{
scanf("%lld %lld", &f[i].A, &f[i].B);
}
sort(f + 1, f + n + 1, cmp);
for(long long i = 1;i <= n; i++)
{
sum[i][0] = sum[i - 1][0] + f[i].A;
sum[i][1] = sum[i - 1][1] + f[i].B;
}
for(long long i = 1;i <= m; i++)
{
scanf("%lld", &c[i]);
}
for(long long i = 1;i <= m; i++)
{
int l = Put(c[i], i, 1);
if(c[i] >= f[l].A && l <= n)
{
insert(l, i);
}
}
for(long long i = 1;i <= n; i++)
{
for(long long j = h[i];j;)
{
long long pos = p[j];
long long x = find(c[pos], i);
c[pos] -= sum[x][0] - sum[i - 1][0];
ans[pos] += sum[x][1] - sum[i - 1][1];
int l = Put(c[pos], pos, x + 1);
int now = last[j];
if(c[pos] >= f[l].A && l <= n)
{
change(j, l);
}
j = now;
}
}
for(long long i = 1;i <= m; i++)
{
printf("%lld\n", ans[i]);
}
return 0;
}
|