Algoogle

Algorithm for Programming Contest

JOI 春合宿 2012 Fish

Category: JOI Tag: inchworm-method, math

Fish

問題概要


N匹の魚がいる.
これらは赤, 青, 緑のいずれかの色になっている.
魚は体長が自分の2倍以上ある魚に食べられてしまうので一緒にできない.
一緒にできる魚の色の組合せを求めよ

解法


setにalgorithmのlower_boundを使っていてTLE死した.

ある魚に対してそれより小さい魚のうち一緒にいられる魚を考える.
この時赤がr匹, 青がb匹, 緑がg匹いるとするとその選び方は3辺の長さがr, b, gの直方体の内部の格子点の数に一致する(=3辺がr+1,b+1,g+1の直方体の体積).
これは赤, 青, 緑の選ぶ数に対して頂点が選べることからわかる.
この組は魚の体長をソートしておけばしゃくとり法する感じで求められる.

よってそのようなものを全て列挙して, 直方体を重ねあわせた体積を求める問題になる.
上から下に積分していけば, 各イベント点(各直方体のてっぺん)で長方形の和をとっていくことで断面が求められる.
各直方体は軸に接するように置いていると考えれば, 断面の長方形の和は各長方形の右上を保存しておけばよい.
この点列は内部に含まれるものを除けば階段状になっているので, 長方形を追加するときにすぐ下の段(右の段)にくる長方形は2分探索で求められる.
そこから1つずつ左に見ていき, 高さを積分していくことで増加分の面積を求める.
すぐ上の段を見つけたら間に今作った新しい段に完全に含まれる段を取り除く.

コード


(fish.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
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

struct cube
{
        int p[3];
        cube(int x, int y, int z){
                p[0] = x;
                p[1] = y;
                p[2] = z;
        }
        bool operator<(const cube &c)const{ return p[2] > c.p[2];}
};

int n;
pii seq[1<<19];
vector<cube> cs;
set<pii> ps;

void gen_cube()
{
        sort(seq, seq+n);
        int l = 0, r = 0;
        cube c(1,1,1);
        while(r < n) {
                c.p[seq[r].second]++;
                while(l < r and seq[l].first*2 <= seq[r].first) c.p[seq[l++].second]--;
                r++;
                cs.push_back(c);
        }
        cs.push_back(cube(0,0,0));
        sort(begin(cs),end(cs));
}

long long solve()
{
        gen_cube();
        ps.insert(pii(0,1000000001));
        ps.insert(pii(1000000001,0));
        long long ans = -1, pz = 0, area = 0;
        for(auto &e: cs) {
                int x = e.p[0], y = e.p[1], z = e.p[2];
                ans += (pz-z)*area;
                pz = z;
                auto lb = ps.lower_bound(pii(x,y)), ub = lb;
                int py = lb->second, px = x;
                if(py >= y) continue;
                while(lb-- != begin(ps)) {
                        int nx = lb->first, ny = lb->second;
                        area += 1LL*(px-nx)*(y-py);
                        if(ny > y) break;
                        py = ny;
                        px = nx;
                }
                ps.erase(++lb,ub);
                ps.insert(ub, pii(x,y));
        }

        return ans;
}

void input()
{
        cin >> n;
        char c; int x, y;
        for (int i = 0; i < n; i++) {
                cin >> x >> c;
                y = (c == 'R')? 0: (c == 'G')? 1: 2;
                seq[i] = pii(x,y);
        }
}

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

Comments