hihoCoder Challenge 9 register

Ended

Participants:154

Verdict:Accepted
Submitted:2015-03-01 19:20:59

Lang:G++

Edit
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
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
int n, m;
const int MAXN = 100005;
struct P {int x, num; } 
pa[MAXN], pb[MAXN];
bool cmp(P a, P b) {return a.x < b.x;}
int main() {
//  freopen("in.txt","r",stdin);
    int T;
    scanf("%d", &T);
    while (T--) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) 
        scanf("%d%d", &pa[i].x, &pa[i].num);
    for (int i = 1; i <= m; ++i)
        scanf("%d%d", &pb[i].x, &pb[i].num);
    sort(pa + 1, pa + n + 1, cmp);
    sort(pb + 1, pb + m + 1, cmp);
    LL ans = 0, nowans = 0; int tmp = 1;
    for (int i = 1; i <= n; ++i) {
        while (tmp <= m && pa[i].x > pb[tmp].x) nowans += pb[tmp].num, tmp ++;
        ans += 1ll * pa[i].num * nowans;
    }
    cout<<ans<<endl;
    }
    return 0;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX