@Jerusalem 2016-02-14T20:18:41.000000Z 字数 1689 阅读 1300

### Vol6

BZOJ1107

#include <cstdio>#include <cstdlib>#include <cmath>#include <cstring>#include <algorithm>#include <iostream>using namespace std;const int maxn=100005,INF=0x3f3f3f3f;struct Node{    int high;    int Num;    Node(){        high=Num=0;    }    Node(int high_,int num_){        high=high_;        Num=num_;    }    bool operator <(const Node& a)const{        if(high==a.high)            return Num<a.Num;         return high>a.high;    }};Node l[maxn],r[maxn];int g[maxn];int lt[maxn],rt[maxn];int nl,nr;int n,m,k,p;void Clear(){    memset(g,0x3f,sizeof(g));    g[0]=0;}int Find(int key,int size){    int l=0,r=size;    while(l+1<r){        int mid=(l+r)/2;        if(g[mid]<key)            l=mid;        else            r=mid;    }    return l;}void First(){    Clear();    for(int i=1;i<=nl;i++){        int calc=Find(l[i].Num,nl)+1;        g[calc]=min(g[calc],l[i].Num);    }    for(int i=0;i<=nl&&g[i]<n;i++)        for(int j=g[i]+1;j<=g[i+1]&&j<=n;j++)            lt[j]=j-i-1;    Clear();    for(int i=1;i<=nr;i++){        int calc=Find(r[i].Num,nr)+1;        g[calc]=min(g[calc],r[i].Num);    }    for(int i=0;i<=nr&&g[i]<n;i++)        for(int j=g[i]+1;j<=g[i+1]&&j<=n;j++)            rt[n-j+1]=j-i-1;}void Solve(){    int ans=0;    //for(int i=1;i<=n;i++)    //  printf("%d %d\n",rt[i],lt[i]);    for(int i=1,j=1;i<=n;i++){        while(j<=i&&rt[j]+lt[i]>k)            j++;         ans=max(ans,i-j+1);    }    for(int i=1;i<=n;i++)        if(lt[i]==0&&rt[i]==0)            ans--;    printf("%d\n",ans);}void Readdata(){    freopen("loli.in","r",stdin);    scanf("%d%d%d%d",&n,&m,&p,&k);    for(int i=1;i<=p;i++){        int a,b,c;        scanf("%d%d%d",&a,&b,&c);        if(c==1)            l[++nl]=Node(b,a);        else            r[++nr]=Node(b,n-a);    }    sort(l+1,l+nl+1);    sort(r+1,r+nr+1);}void Close(){    fclose(stdin);    fclose(stdout);}int main(){    Readdata();    First();    Solve();    Close();    return 0;}

• 私有
• 公开
• 删除