Contest Duration: ~ (local time) (90 minutes) Back to Home

Submission #524607

Source Code Expand

Copy
```#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <sstream>
#include <map>
#include <set>
#include <vector>
#include <cmath>

using namespace std;

struct vertex{
int X;
int Y;
};

int	gcd(int	a, int b){
while( b ){
int	m = a % b;
a = b;
b = m;
}
return a;
}

int	lcm(int a, int	b){
return (a*b)/gcd(a,b);
}

int isPrim(int a){
if(a==1){
return 0;
}
for(int i=2;i<=(a+1)/2;i++){
if(a%i==0){
return 0;
}
}
return 1;
}

int main(int argc, const char * argv[])
{
//std::ios::sync_with_stdio(false);
//scanf("%s",S);
//scanf("%d",&N);
//getline(cin, target);
//cin >> x >> y;
//ここから

int N,M;
cin >> N >> M;
int s[100000];
int t[100000];

for(int i=0;i<M;i++){
cin >> s[i];
cin >> t[i];
}

int zou[300000];
int kasan[300000];

vector<int>zero;
zero.clear();
for(int i=0;i<300000;i++){
zou[i]=0;
}
for(int i=0;i<M;i++){
zou[s[i]]++;
zou[t[i]+1]--;
}
for(int i=1;i<=N;i++){
if(i==1){
kasan[i]=zou[i];
}else{
kasan[i]=kasan[i-1]+zou[i];
}
if(kasan[i]==1){
zero.push_back(i);
}
}
vector<int>ans;
ans.clear();
int anscnt=0;
for(int i=0;i<M;i++){
int flag=0;
for(int j=0;j<zero.size();j++){
if(s[i]<=zero[j] && zero[j]<=t[i]){
flag=1;
break;
}
}
if(flag==0){
ans.push_back(i+1);
anscnt++;
}
}

cout << anscnt << endl;
for(int i=0;i<ans.size();i++){
cout << ans[i]<< endl;

}
//cout << endl;

//ここまで
//cout << "ans" << endl;改行含む
//printf("%.0f\n",ans);//小数点以下表示なし
//printf("%.7f",p);
//printf("%f\n",pow(2,ans.size()));

return 0;
}
```

#### Submission Info

Submission Time 2015-10-10 22:29:53+0900 B - ドキドキデート大作戦高橋君 ikeha C++ (GCC 4.9.2) 0 2178 Byte TLE 2041 ms 6076 KB

#### Test Cases

Set Name Score / Max Score Test Cases
Case Name Status Exec Time Memory