Submission #1029639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029639		sleepntsheep	Roller Coaster Railroad (IOI16_railroad)	C11	0 / 100	124 ms	11572 KiB

railroad

#include "railroad_c.h"
#include<stdio.h>
#include <stdlib.h>

int C(const void*i, const void*j){return*(const int*)i-*(const int*)j;}

int lb(int*a,int n,int x){
    int l=-1,u=n,m;
    while(u-l>1)(a[m=l+(u-l)/2]<x)?(l=m):(u=m);
    return u;
}

long long plan_roller_coaster(int n, int *s, int *t) {
    static int lef[1000000],rgt[1000000], lc[1000000];


    /*compress*/
    for(int i=0;i<n;++i) lef[2*i]=s[i],lef[2*i+1]=t[i];
    qsort(lef,2*n,sizeof*lef,C);
    for(int i=0;i<n;++i) s[i]=lb(lef,2*n,s[i]),t[i]=lb(lef,2*n,t[i]),++s[i],++t[i];


    /*yes*/
    int lo=0,ro=0;
    for (int i = 0; i < n; ++i)
        if (s[i]<=t[i])
            lef[lo] = i, lc[lo++] = s[i];

    for (int i = 0; i < n; ++i) {
        if (s[i]>t[i]){
            if (lb(lc,lo,s[i]-1)-lb(lc,lo,t[i]))
                rgt[ro++]=i;
            else
                lef[lo]=i,lc[lo++]=s[i]=t[i];
        }
    }

    static int diff[1000000];
    for(int i=0;i<sizeof diff/sizeof*diff;++i)diff[i]=0;

    for (int i=0;i<lo;++i)
        ++diff[s[lef[i]]],--diff[1+t[lef[i]]];
    for(int i=0;i<ro;++i)
        --diff[t[rgt[i]]],++diff[1+s[rgt[i]]];
    for(int i=1;i<sizeof diff/sizeof*diff;++i){
        diff[i]+=diff[i-1];
        if(diff[i]>1)return 1;
    }


    return 0;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 23
• Subtask 3: 0 / 30
• Subtask 4: 0 / 36