Algoogle

Algorithm for Programming Contest

JOI 春合宿 2010 Hide-and-seek

Category: JOI Tag: segment-tree

Hide-and-seek

問題概要


2次元に広がるマスに障害物が置かれている.
いまy=0のいずれかのマスからy>0の方向に攻撃が一直線に来る.
各攻撃は障害物をどれだけ破壊できるか決まっている.
障害物は中に入ることができるのでその数+1個目の障害物に隠れれば敵の攻撃を防げる.
敵の攻撃を防げるようなマスのうちy座標が最小のものを求めよ.
複数ある場合はx座標がそのなかで小さい方を求めよ.

解法


マスは大きいので愚直に計算することはできない.
y座標に対してx座標と障害物の数が小さいことに注目する.
障害物をy座標の昇順に設置していくことを考える.
障害物を設置するとき, そのx座標の区間にその直前までの障害物の重なりの最大が現れるなら, その重なり分と等しい攻撃力の攻撃から隠れるには現在の障害物を選ぶべき(これでy座標が決まる).
区間の最大はSegment-Treeで管理すれば良い.
そのとき, その値をとる一番小さいxも返すようにしてやれば答えが求まる.

Segment-Treeはその区間に一度に足された数とその区間での最大値とそのx座標を持つようなものを考えれば良い.

コード


(hideandseek.cpp) download
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
108
109
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

struct segtree
{
        int N;
        vector<int> add;
        vector<pii> dat;
        segtree(int n) {
                N = 1;
                while(N < n) N *= 2;
                dat.assign(2*N-1, pii(0,0));
                init(0,N,0);
                add.assign(2*N-1, 0);
        }

        void init(int l, int r, int k)
        {
                dat[k].second = -l;
                if(r-l==1) return;
                init(l,(l+r)/2,2*k+1);
                init((l+r)/2,r,2*k+2);
        }

        void update(int a, int b, int x) { update(a,b,0,N,0,x);}
        pii update(int a, int b, int l, int r, int k, int x) {
                if(r <= a or b <= l) return pii(-1,-1);
                if(a <= l and r <= b) {
                        add[k] += x;
                        dat[k].first += x;
                        return dat[k];
                }
                int m = (l+r)/2;
                pii tmp = max(update(a,b,l,m,2*k+1,x), update(a,b,m,r,2*k+2,x));
                tmp.first += add[k];
                dat[k] = max(dat[k], tmp);
                return dat[k];
        }

        pii query(int a, int b){
                pii ret = query(a, b, 0, N, 0);
                ret.second *= -1;
                return ret;
        }
        pii query(int a, int b, int l, int r, int k) {
                if(r <= a or b <= l) return pii(-1,-1);
                if(a <= l and r <= b) return dat[k];
                int m = (l + r) / 2;
                pii ret = max(query(a, b, l, m, k*2+1), query(a, b, m, r, k*2+2));
                ret.first += add[k];
                return ret;
        }
};

struct wall
{
        int y, l, r;
        bool operator<(const wall &a)const{
                if(y != a.y) return y < a.y;
                return l < a.l;
        }
};

int n, m;
vector<wall> obj;
vector<pii> ans;
priority_queue<pii, vector<pii>, greater<pii>> weap;

void solve()
{
        sort(begin(obj),end(obj));
        segtree st(100000);
        ans.assign(m, pii(-2,-2));
        for(auto &o: obj) {
                pii p = st.query(o.l, o.r);
                while(!weap.empty()) {
                        pii q = weap.top();
                        if(q.first > p.first) break;
                        weap.pop();
                        ans[q.second] = pii(p.second, o.y);
                }
                st.update(o.l, o.r, 1);
        }
        for(auto &e: ans) cout << e.first+1 << " " << e.second+1 << endl;
}

void input()
{
        cin >> n >> m;
        for (int i = 0; i < n; i++) {
                int x, y, w;
                cin >> x >> y >> w;
                obj.push_back((wall){y-1,x-1,x-1+w});
        }
        for (int i = 0; i < m; i++) {
                int a; cin >> a;
                weap.push(pii(a,i));
        }
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        solve();
        return 0;
}

Comments