Submission #524415


Source Code Expand

Copy
#include <stdio.h>
#include <math.h>

int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	int a[300005]={0};
	int l[100001],r[100001];
	int nn=sqrt(nn)+1;
	int aa[10001];
	for(int i=0,f,ff;i<m;i++){
		scanf("%d%d",&f,&ff);
		l[i]=f,r[i]=ff;
		a[f]++;a[ff+1]--;
	}
	int inf=1<<30;
	n++;
	for(int i=1;i<n;i++)a[i]+=a[i-1];
	for(int i=0;i*nn<n;i++)aa[i]=inf;
	for(int i=0;i*nn<n;i++){
		for(int j=i*nn,ln=(i+1)*nn;j<ln;j++){
			if(aa[i]>a[j])aa[i]=a[j];
		}
	}
	int ans=0;
	for(int i=0;i<m;i++){
		int f=inf,mm=(l[i]+nn-1)/nn*nn,mmm=r[i]/nn;;
		for(int j=l[i];j<mm&&j<=r[i];j++){
			if(f>a[j])f=a[j];
		}
		if(f==1)continue;
		for(int j=(l[i]+nn-1)/nn;j<mmm;j++){
			if(f>aa[j])f=aa[j];
		}
		if(f==1)continue;
		for(int j=mmm;j<=r[i];j++){
			if(f>a[j])f=a[j];
		}
		if(f>1){l[i]=0;ans++;}
	}
	printf("%d\n",ans);
	for(int i=0;i<m;i++){
		if(!l[i])printf("%d\n",i+1);
	}
	return 0;
}

Submission Info

Submission Time
Task B - ドキドキデート大作戦高橋君
User rikku
Language C++ (GCC 4.9.2)
Score 0
Code Size 919 Byte
Status
Exec Time 2035 ms
Memory 2840 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:6:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
                     ^
./Main.cpp:12:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&f,&ff);
                       ^

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt
Subtask1 0 / 30 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt
All 0 / 70 subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt 26 ms 1824 KB
subtask0_sample_02.txt 27 ms 1812 KB
subtask0_sample_03.txt 26 ms 1948 KB
subtask1_01.txt 61 ms 2648 KB
subtask1_02.txt 113 ms 2592 KB
subtask1_03.txt 2035 ms 2736 KB
subtask1_04.txt 2034 ms 2840 KB
subtask1_05.txt 2035 ms 2724 KB
subtask1_06.txt 26 ms 1948 KB
subtask1_07.txt 27 ms 1820 KB
subtask1_08.txt 27 ms 1828 KB
subtask1_09.txt 27 ms 1836 KB
subtask2_01.txt 109 ms 2596 KB
subtask2_02.txt 195 ms 2716 KB
subtask2_03.txt 26 ms 1952 KB
subtask2_04.txt 25 ms 1956 KB
subtask2_05.txt 27 ms 1868 KB
subtask2_06.txt 27 ms 1828 KB
subtask2_07.txt 26 ms 1828 KB
subtask2_08.txt 2034 ms 2724 KB