首页 > 代码库 > Codeforces12D--三维线段树

Codeforces12D--三维线段树

#include <stdio.h>#include <stdlib.h>#include <math.h>#include <time.h>#include <string.h>#include <iostream>#include <vector>#include <list>#include <stack>#include <queue>#include <map>#include <set>#include <algorithm>typedef short int int16;///32767typedef int int32;///2147483647typedef long long int64;///9223372036854775807const double PI=acos(-1.0);///3.141593const long long MOD=(long long)1E9+7LL;///1000000007int isdigit(int c);int islower(int c);int isupper(int c);int tolower(int c);int toupper(int c);template <class T> T Susake_pow(T a,T b)///pow{T res;if(b==0) return 1;else while((b&1)==0){b>>=1;a*=a;}res=a;b>>=1;while(b!=0){a*=a;if((b&1)!=0)res*=a;b>>=1;}return res;}template<class T> inline T gcd(T a,T b)///gcd{if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}template<class T> inline T lcm(T a,T b)///lcm{if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}template<class T> inline char *Susake_nsystem(T n)///itoa(26){T t=0,i;char *s,*p;s=(char *)malloc(sizeof(char)*1000);p=(char *)malloc(sizeof(char)*1000);while(n){s[t]=n%26+64;if(s[t]==64){s[t]+=26;n-=26;}t++;n/=26;}s[t]=\0;for(i = 0; i < t; i++)p[i]=s[t-1-i];p[i]=\0;free(s);return p;}int Susake_system(char *s)///atoi(26){int len=strlen(s),i,sum=0;char p[1000];for(i=0;i<len;i++)p[i]=s[len-1-i]-64;for(i=0;i<len;i++)sum+=p[i]*Susake_pow(26,i);return sum;}int fa[1];template <class T> T union_find(T x)///union_find{return fa[x] == x ? x : fa[x] = union_find(fa[x]);}const int maxn = 500010;const int inf = 1<<30;struct node{    int b,i,l;    bool operator<(const node &x) const    {        if(b==x.b)        {            if(i==x.i)            {                return l < x.l;            }            return i > x.i;        }        return b < x.b;    }}ji[maxn];int main(){    int n;    std::map<int,int> mp;    std::map<int,int>::iterator it;    scanf("%d",&n);    for(int i=1;i<=n;i++)        scanf("%d",&ji[i].b);    for(int i=1;i<=n;i++)        scanf("%d",&ji[i].i);    for(int i=1;i<=n;i++)        scanf("%d",&ji[i].l);    std::sort(ji+1,ji+n+1);    mp[inf] = -inf;    mp[-inf] = inf;    int res = 0;    for(int i=n;i>=1;i--)    {        it = mp.upper_bound(ji[i].i);        if(ji[i].l<it->second)            res++;        else if(mp[ji[i].i]<ji[i].l)        {            mp[ji[i].i] = ji[i].l;            for(it = --mp.lower_bound(ji[i].i);it->second<=ji[i].l;)                mp.erase(it--);        }    }    printf("%d\n",res);    return 0;}

 

Codeforces12D--三维线段树