Submission #1029639

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1029639	2024-07-21 06:54:13	sleepntsheep	Roller Coaster Railroad (IOI16_railroad)	C11	0 / 100	124 ms	11572 KiB

railroad

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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]){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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