Submission #1791744

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define lol(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;
using namespace std;
#define N (1<<19)
int seg[1<<20];
void init(){
	lol(i,2*N)seg[i]=mod;
}
void update(int i,int x){
	i+=N-1;
	seg[i]=x;
	while(i){
		i=(i-1)/2;
		seg[i]=min(seg[i],x);
	}
}
int rmq(int left,int right,int a,int b,int k){
	if(left<=a&&b<=right)return seg[k];
	if(right<=a||b<=left)return mod;
	int m=(a+b)/2;
	return min(rmq(left,right,a,m,k*2+1),rmq(left,right,m,b,k*2+2));
}
int qry(int left,int right){return rmq(left,right,0,N,0);}

int a[300010],n,m;
int x[100010],y[100010];
int main(){
	init();
	cin>>n>>m;
	lol(i,n)a[i]=0;
	lol(i,m){
		cin>>x[i]>>y[i];
		a[x[i]-1]++,a[y[i]]--;
	}
	int cls=0;
	lol(i,n){
		cls+=a[i];
		update(i,cls);
	}
	int cnt=0;
	lol(i,m)if(qry(x[i]-1,y[i])>1)cnt++;
	cout<<cnt<<endl;
	lol(i,m)if(qry(x[i]-1,y[i])>1)cout<<i+1<<endl;
	return 0;
}

Submission Info

Judge Result