UVA11020 Efficient Solutions

思路

先判断一个点能不能插入，能插入的话删除所有因为它而没有优势的点

注意

写

    S.erase(it);

    it++;

会RE

要写

    S.erase(it++);

代码

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <set>

using namespace std;

multiset<pair<int,int> > S;

int n;

int main(){

    // freopen("test.in","r",stdin);

    // freopen("test.out","w",stdout);

    int T,cnt=0;

    scanf("%d",&T);

    while(T--){

        cnt++;

        scanf("%d",&n);

        S.clear();

        printf("Case #%d:\n",cnt);

        for(int i=1;i<=n;i++){

            int x,y;

            scanf("%d %d",&x,&y);

            auto it = S.lower_bound(make_pair(x,y));

            if(it==S.begin()){

                S.insert(make_pair(x,y));

                for(auto it2=S.upper_bound(make_pair(x,y));it2!=S.end();){

                    // printf("it1 %d,%d\n",(*it2).first,(*it2).second);

                    if((*it2).second>=y)

                        S.erase(it2++);

                    else

                        break;

                }

            }

            else{

                it--;

                if((*it).second>y){

                    S.insert(make_pair(x,y));

                    for(auto it2=S.upper_bound(make_pair(x,y));it2!=S.end();){

                        // printf("it2 %d,%d\n",(*it2).first,(*it2).second);

                        if((*it2).second>=y)

                            S.erase(it2++);

                        else

                            break;

                    }

                }

            }

            printf("%d\n",S.size());

        }

        if(T)

            printf("\n");

    }

    return 0;

}