Submission #13650

#	Time	Username	Problem	Language	Result	Execution time	Memory
13650		dohyun0324	Fortune Telling 2 (JOI14_fortune_telling2)	C++98	100 / 100	369 ms	30772 KiB

fortune_telling2

#include<stdio.h>
#include<algorithm>
using namespace std;
int p,cnt,w,t,n,k,a[200010],b[200010],c[200010],tree[2000010],tree2[2000010],sw[200010],a2[200010],b2[200010];
long long sum;
struct data
{
    int x,y;
    bool operator<(const data&r)const
    {
        return x<r.x;
    }
}arr[600010];
data pos[600010];
void update(int x,int p)
{
    x+=t-1; tree[x]=p; x/=2;
    while(x){
        tree[x]=max(tree[x*2],tree[x*2+1]);
        x/=2;
    }
}
void update2(int x)
{
    while(x<=t){
        tree2[x]++;
        x+=x&(-x);
    }
}
int query(int x,int y,int k,int s,int e)
{
    if(x>e || y<s) return 0;
    if(s<=x && y<=e) return tree[k];
    return max(query(x,(x+y)/2,k*2,s,e),query((x+y)/2+1,y,k*2+1,s,e));
}
int query2(int x)
{
    int hap=0;
    while(x){
        hap+=tree2[x];
        x-=x&(-x);
    }
    return hap;
}
int main()
{
    int i,j,s;
    scanf("%d %d",&n,&k);
    for(i=1;i<=n;i++){
        scanf("%d %d",&a[i],&b[i]);
        if(a[i]>b[i]) swap(a[i],b[i]), sw[i]=1;
        a2[i]=a[i], b2[i]=b[i];
        arr[++w].x=a[i]; arr[w].y=i*2;
        arr[++w].x=b[i]; arr[w].y=i*2+1;
    }
    for(i=1;i<=k;i++){
        scanf("%d",&c[i]);
        arr[++w].x=c[i]; arr[w].y=-i;
    }
    sort(arr+1,arr+w+1);
    for(i=1;i<=w;i++)
    {
        if(arr[i].x!=arr[i-1].x) cnt++;
        if(arr[i].y>0){
            if(arr[i].y%2==0) a[arr[i].y/2]=cnt;
            else b[arr[i].y/2]=cnt;
        }
        else c[-arr[i].y]=cnt;
    }
    for(t=1;t<=cnt;t*=2);
    for(i=1;i<=k;i++) update(c[i],i);
    for(i=1;i<=n;i++){
        pos[i].x=query(1,t,1,a[i],b[i]-1); pos[i].y=i;
    }
    sort(pos+1,pos+n+1); p=k;
    for(i=n;i>=1;i--){
        for(j=p;j>=pos[i].x+1;j--) update2(c[j]);
        p=pos[i].x;
        s=query2(t)-query2(b[pos[i].y]-1);
        if(pos[i].x){
            if(s%2==0) sum+=b2[pos[i].y];
            else sum+=a2[pos[i].y];
        }
        else{
            if((sw[pos[i].y]+s)%2==0) sum+=a2[pos[i].y];
            else sum+=b2[pos[i].y];
        }
    }
    printf("%lld",sum);
    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65