oj.uz

Submission #13650

# Submission time Handle Problem Language Result Execution time Memory
13650 2015-02-27T03:18:46 Z dohyun0324 Fortune Telling 2 (JOI14_fortune_telling2) C++
100 / 100
 369 ms 30772 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 30772 KB Output is correct
2 Correct 0 ms 30772 KB Output is correct
3 Correct 0 ms 30772 KB Output is correct
4 Correct 0 ms 30772 KB Output is correct
5 Correct 0 ms 30772 KB Output is correct
6 Correct 0 ms 30772 KB Output is correct
7 Correct 0 ms 30772 KB Output is correct
8 Correct 0 ms 30772 KB Output is correct
9 Correct 0 ms 30772 KB Output is correct
10 Correct 0 ms 30772 KB Output is correct
11 Correct 0 ms 30772 KB Output is correct
12 Correct 3 ms 30772 KB Output is correct
13 Correct 0 ms 30772 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 30772 KB Output is correct
2 Correct 35 ms 30772 KB Output is correct
3 Correct 48 ms 30772 KB Output is correct
4 Correct 48 ms 30772 KB Output is correct
5 Correct 70 ms 30772 KB Output is correct
6 Correct 69 ms 30772 KB Output is correct
7 Correct 70 ms 30772 KB Output is correct
8 Correct 56 ms 30772 KB Output is correct
9 Correct 46 ms 30772 KB Output is correct
10 Correct 52 ms 30772 KB Output is correct
11 Correct 48 ms 30772 KB Output is correct
12 Correct 49 ms 30772 KB Output is correct
13 Correct 40 ms 30772 KB Output is correct
14 Correct 50 ms 30772 KB Output is correct
15 Correct 48 ms 30772 KB Output is correct
16 Correct 54 ms 30772 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 30772 KB Output is correct
2 Correct 156 ms 30772 KB Output is correct
3 Correct 196 ms 30772 KB Output is correct
4 Correct 369 ms 30772 KB Output is correct
5 Correct 67 ms 30772 KB Output is correct
6 Correct 346 ms 30772 KB Output is correct
7 Correct 352 ms 30772 KB Output is correct
8 Correct 337 ms 30772 KB Output is correct
9 Correct 319 ms 30772 KB Output is correct
10 Correct 365 ms 30772 KB Output is correct
11 Correct 354 ms 30772 KB Output is correct
12 Correct 369 ms 30772 KB Output is correct
13 Correct 315 ms 30772 KB Output is correct
14 Correct 261 ms 30772 KB Output is correct
15 Correct 284 ms 30772 KB Output is correct
16 Correct 271 ms 30772 KB Output is correct
17 Correct 272 ms 30772 KB Output is correct
18 Correct 247 ms 30772 KB Output is correct
19 Correct 275 ms 30772 KB Output is correct
20 Correct 273 ms 30772 KB Output is correct