2016北京网络赛 hihocoder 1391 Countries 树状数组

Countries

描述

There are two antagonistic countries, country A and country B. They are in a war, and keep launching missiles towards each other.

It is known that country A will launch N missiles. The i-th missile will be launched at time Tai. It flies uniformly and take time Taci from one country to the other. Its damage capability is Dai.

It is known that country B will launch M missiles. The i-th missile will be launched at time Tbi.

It flies uniformly and takes time Tbci from one country to the other. Its damage capability is Dbi.

Both of the countries can activate their own defending system.

The defending system of country A can last for time TA, while The defending system of country B can last for time TB.

When the defending system is activated, all missiles reaching the country will turn around and fly back at the same speed as they come.

At other time, the missiles reaching the country will do damages to the country.
(Note that the defending system is still considered active at the exact moment it fails)

Country B will activate its defending system at time X.

When is the best time for country A to activate its defending system? Please calculate the minimal damage country A will suffer.

输入

There are no more than 50 test cases.

For each test case:

The first line contains two integers TA and TB, indicating the lasting time of the defending system of two countries.

The second line contains one integer X, indicating the time that country B will active its defending system.

The third line contains two integers N and M, indicating the number of missiles country A and country B will launch.

Then N lines follow. Each line contains three integers Tai, Taci and Dai, indicating the launching time, flying time and damage capability of the i-th missiles country A launches.

Then M lines follow. Each line contains three integers Tbi, Tbci and Dbi, indicating the launching time, flying time and damage capability of the i-th missiles country B launches.

0 <= TA, TB, X, Tai, Tbi<= 100000000

1 <= Taci, Tbci <= 100000000

0 <= N, M <= 10000

1 <= Dai, Dbi <= 10000

输出

For each test case, output the minimal damage country A will suffer.

提示

In the first case, country A should active its defending system at time 3.

Time 1: the missile is launched by country A.

Time 2: the missile reaches country B, and country B actives its defending system, then the missile turns around.

Time 3: the missile reaches country A, and country A actives its defending system, then the missile turn around.

Time 4: the missile reaches country B and turns around.

Time 5: the missile reaches country A and turns around.

Time 6: the missile reaches country B, causes damages to country B.

样例输入

样例输出

0
17

Emacs Normal Vim

题意：

题解：

　　关键点就在于要：假设出A时刻处于防御状态

　　那么我们可以O(1)处理出每一个导弹最开始砸向A，最后一次砸向A 形成些许个区间段，当防御系统完全覆盖这段的时候才可以避免这只导弹

　　那么就等于确定一个长度K的使得这个避免的导弹伤害最大

　　这个可以前缀和做出来

　　队友提示了树状数组做法

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<map>
using namespace std;

#pragma comment(linker, "/STACK:102400000,102400000")
#define ls i<<1
#define rs ls | 1
#define mid ((ll+rr)>>1)
#define pii pair<int,int>
#define MP make_pair

typedef long long LL;
const long long INF = 1e18;
const double Pi = acos(-1.0);
const int N = 1e6+10, M = 1e2+10, mod = 1e9+7, inf = 2e9;

LL n,m,end_b,C[N],star_b,ans,sum[N],san[N];
LL V[N];

int all;
int numa,numb;
struct node {
        LL fi,se,d;
        node() {}
        node(LL fi,LL se,LL d) {
            this->fi=fi;this->se=se;this->d=d;
        }
        bool operator < (const node &r) const {
                return se<r.se;
        }
};
vector< node > G;
vector< pii > E[N];
map< LL , int > mp;

LL haxi(LL x) {
        return lower_bound(san+1,san+all+1,x) - san;
}
LL ask(int x) {
        LL S = 0;
        if(x <= 0) return 0;
        for(int i = x; i; i-=i&(-i)) S += C[i];
        return S;
}
void update(int x,LL c) {
        for(int i = x; i< N; i+=i&(-i)) C[i] += c;
}
int main() {
         while(scanf("%lld%lld",&n,&m)!=EOF) {
            scanf("%lld",&star_b);
            end_b = star_b+m;

            ans = 0;G.clear();mp.clear();
            memset(C,0,sizeof(C));
            for(int i = 0; i< N; ++i) E[i].clear();

            scanf("%d%d",&numa,&numb);
            for(int i = 1; i <= numa; ++i) {
                LL s,t,d;
                scanf("%lld%lld%lld",&s,&t,&d);
                if(s+t < star_b) {
                    ans += 0;
                } else if(s+t > end_b) ans+=0;
                else {
                     LL fi = s+2*t,se;
                     if(end_b <= fi) se = fi;
                     else  {
                        LL mo = (end_b - fi)% (2*t);
                        LL md = (end_b - fi)/(2*t);
                        if(mo < t) {
                            se = md*(2*t) + fi;
                        } else {
                            se = (md+1)*(t*2) + fi;
                        }
                     }
                     G.push_back(node{fi,se,d});//cout<<fi<<" "<<se<<endl;
                }
            }

            for(int i = 1; i <= numb; ++i) {
                LL s,t,d;
                scanf("%lld%lld%lld",&s,&t,&d);
                LL fi = s+t;
                 if(s+t+t < star_b) {
                    G.push_back(node{fi,fi,d});
                } else if(s+t+t > end_b) {
                    G.push_back(node{fi,fi,d});
                }
                else {
                    LL se;
                    if(end_b <= fi) se = fi;
                     else  {
                        LL mo = (end_b - fi)% (2*t);
                        LL md = (end_b - fi)/(2*t);
                        if(mo < t) {
                            se = md*(2*t) + fi;
                        } else {
                            se = (md+1)*(t*2) + fi;
                        }
                     }
                    G.push_back(node{fi,se,d});
                }
            }
            all = 0;
            LL sumall = 0;
            for(int i = 0; i < G.size(); ++i) {
                    san[++all] = G[i].fi;
                    san[++all] = G[i].se;
                    san[++all] = G[i].se - n;
                    sumall += G[i].d;
            }
            sort(san+1,san+all+1);
            all = unique(san+1,san+all+1) - san - 1;
            LL ans2 = 0;
            sort(G.begin(),G.end());
            for(int i = 0; i < G.size(); ++i) {
                int pos = haxi(G[i].se);
                update(haxi(G[i].fi),G[i].d);
                ans2 = max(ans2,ask(pos) - ask(haxi(G[i].se-n)-1));
            }
            printf("%lld
",ans + sumall - ans2);

        }
        return 0;
}

/*

0 0
1
0 2
5 1 100
6 1 100

0 0
3
1 1
1 2 10
2 3 8
0 0
4
1 1
1 2 10
2 3 8
2 2
2
1 0
1 1 10
4 5
3
2 2
1 2 10
1 5 7
1 3 2
0 4 8
*/