JOI春合宿「Fishは強実装」はウソ

http://d.hatena.ne.jp/JAPLJ/20120214/1329229478
この記事に対抗して書いてみました。

去年のJOI春合宿Day 1では3問の問題が出題されました。
このうちJOI flagは合宿で一番簡単な問題で(それでも例年の合宿の簡単な問題よりは難しく、解けなかった)、Building 2は準急さんもTLEするヤバ問でした。
2問目のFishは満点は2人で、難化した去年の合宿の中では(ここ重要)やさしい部類の問題でした。
ですが、「iterationがむずかしい」との理由から「強実装」に分類されることが多いです。
去年競技プログラミング歴4か月でsegtreeも書けずに合宿に臨んだ自分は、解法は大体分かったもののstd::setを使ったことがなかったので使い方がわからず、実装できませんでした。
その後setの使い方を知り、解いてみたところ、大した実装はせずに満点を取ることができました。

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>pii;
typedef pair<ll,pii>pi3;
int main()
{
    int num;
        scanf("%d",&num);
        vector<int>va,vb,vc;
        for(int i=0;i<num;i++)
        {
                int za;
                char zb;
                scanf("%d %c",&za,&zb);
                if(zb=='R')
                {
                        va.push_back(za);
                }
                if(zb=='G')
                {
                        vb.push_back(za);
                }
                if(zb=='B')
                {
                        vc.push_back(za);
                }
        }
        sort(va.begin(),va.end());
        sort(vb.begin(),vb.end());
        sort(vc.begin(),vc.end());
        vector<pi3>vec;
        for(int i=0;i<va.size();i++)
        {
                int lowa=lower_bound(va.begin(),va.end(),va[i])-va.begin();
                int uppa=upper_bound(va.begin(),va.end(),va[i]*2-1)-va.begin();
                int lowb=lower_bound(vb.begin(),vb.end(),va[i])-vb.begin();
                int uppb=upper_bound(vb.begin(),vb.end(),va[i]*2-1)-vb.begin();
                int lowc=lower_bound(vc.begin(),vc.end(),va[i])-vc.begin();
                int uppc=upper_bound(vc.begin(),vc.end(),va[i]*2-1)-vc.begin();
                vec.push_back(make_pair(uppa-lowa+1,make_pair(uppb-lowb+1,uppc-lowc+1)));
        }
        for(int i=0;i<vb.size();i++)
        {
                int lowa=lower_bound(va.begin(),va.end(),vb[i])-va.begin();
                int uppa=upper_bound(va.begin(),va.end(),vb[i]*2-1)-va.begin();
                int lowb=lower_bound(vb.begin(),vb.end(),vb[i])-vb.begin();
                int uppb=upper_bound(vb.begin(),vb.end(),vb[i]*2-1)-vb.begin();
                int lowc=lower_bound(vc.begin(),vc.end(),vb[i])-vc.begin();
                int uppc=upper_bound(vc.begin(),vc.end(),vb[i]*2-1)-vc.begin();
                vec.push_back(make_pair(uppa-lowa+1,make_pair(uppb-lowb+1,uppc-lowc+1)));
        }
        for(int i=0;i<vc.size();i++)
        {
                int lowa=lower_bound(va.begin(),va.end(),vc[i])-va.begin();
                int uppa=upper_bound(va.begin(),va.end(),vc[i]*2-1)-va.begin();
                int lowb=lower_bound(vb.begin(),vb.end(),vc[i])-vb.begin();
                int uppb=upper_bound(vb.begin(),vb.end(),vc[i]*2-1)-vb.begin();
                int lowc=lower_bound(vc.begin(),vc.end(),vc[i])-vc.begin();
                int uppc=upper_bound(vc.begin(),vc.end(),vc[i]*2-1)-vc.begin();
                vec.push_back(make_pair(uppa-lowa+1,make_pair(uppb-lowb+1,uppc-lowc+1)));
        }
        sort(vec.begin(),vec.end());
        reverse(vec.begin(),vec.end());
        set<pii>se;
        se.insert(make_pair(0,2000000000));
        se.insert(make_pair(2000000000,0));
        ll ans=0;
        ll men=0;
        for(int i=0;i<num;i++)
        {
                set<pii>::iterator it=se.lower_bound(vec[i].second);
                pii zan=*it;
                if(vec[i].second.first>zan.first||vec[i].second.second>zan.second)
                {
                        for(;;)
                        {
                                it--;
                                zan=*it;
                                if(vec[i].second.first>=zan.first&&vec[i].second.second>=zan.second)
                                {
                                        it--;
                                        pii zan2=*it;
                                        it++;
                                        it++;
                                        pii zan3=*it;
                                        it--;
                                        men-=(zan.first-zan2.first)*(zan.second-zan3.second);
                                        se.erase(it++);
                                }
                                else
                                {
                                        break;
                                }
                        }
                        it=se.lower_bound(vec[i].second);
                        pii zan3=*it;
                        it--;
                        pii zan2=*it;
                        men+=(vec[i].second.first-zan2.first)*(vec[i].second.second-zan3.second);
                        se.insert(vec[i].second);
                }
                if(i==num-1)
                {
                        ans+=men*vec[i].first;
                }
                else
                {
                        ans+=men*(vec[i].first-vec[i+1].first);
                }
        }
        printf("%lld\n",ans-1);
}

116行あります。116行という時点で、JOIで出る問題としてはとても強実装とは言えないと思います。
しかも65行目くらいまでは直方体を構成しているだけで、この3つの塊はほとんどコピー&ペーストで作られています。(問題名ではない)
setを使う問題を強実装と呼ぶのは、「setを使うことでREしないようにするための場合分けがたくさん必要だから」という理由が多いと思われますが、見ての通り本質部分での場合分けは3つしかありません。これは69,70行目において、setの最初と最後に番兵のようなものを入れているからであり、setは配列と違って添え字でのアクセスをしないため、番兵を入れたからと言って添え字が狂うなどの副作用はありません。
以上の理由から、私は「Fishは強実装」はウソであると主張します。

最後になりますが、kagamizさんにローカルでジャッジをしていただきました。ありがとうございました。