提出 #66325289

---

ソースコード 拡げる

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

#define ll long long
#define ull unsigned long long
#define ji long double
#define st string
#define vi vector<int>
#define vj vector<ji>
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define vii vector<ii>
#define viii vector<iii>
#define vl vector<ll>
#define lll pair<ll,ll>
#define vll vector<lll>
#define vsh vector<sh>
#define vs vector<st>
#define vc vector<char>
#define vb vector<bool>
#define vd vector<double>
#define vvi vector<vi>
using Graph = vvi;
#define vvl vector<vl>
#define vvs vector<vs>
#define vvc vector<vc>
#define vvb vector<vb>
#define vvvi vector<vvi>
#define vvvl vector<vvl>
#define vvvb vector<vvb>
#define vvvvl vector<vvvl>
#define vvvvvl vector<vvvvl>
//using mint = static_modint<M>;
using mint = modint998244353;
#define pq priority_queue
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define rep1(i,n) for(int i=1; i<=(int)(n); i++)
#define sor(A) sort(A.begin(),A.end());
#define rev(A) reverse(A.begin(),A.end());
#define ijo(A,n) *lower_bound(A.begin(),A.end(),n);
#define cho(A,n) *upper_bound(A.begin(),A.end(),n);
#define keta(n) cout << fixed << setprecision(n);
#define yn(f) cout << (f ? "Yes" : "No") << endl
#define YN(f) cout << (f ? "YES" : "NO") << endl

const ll Mod = 998244353;
const ll MOD = 1000000007;
const ll INF = 1'000'000'001'000'000'001;
const double PI = acos(-1);

template<class T> void out(T& A){rep(i,A.size()){if(i) cout<<" "; cout<<A[i];} cout << endl;}

// ***** 数のmax ***************************
//int ~2'147'483'647   2.1...*10^9
//ll ~9'223'372'036'854'775'807   9.2...*10^18

// ***** コンテナ **************************
/* set<st> X;
X.insert(s)  // X.erase(s)  // O(logN)
*begin(X)  // 最小  // *rbegin(X)  // 最大  // O(1)
// map<st,int> X
X[s]=n  // X[s]  // X.erase(s)  // O(logN)
// queue<int> q  // 追加した順
q.push(n)  // while(!q.empty()){cout<<q.front(); q.pop();}  // O(1)
// stack<int> s  // 追加した逆順
s.push(n)  // while(!s.empty()){cout<<s.top(); s.pop();}  // O(1)
// priority_queue<int> pq  // 大きい順
// priority_queue<int,vector<int>,greater<int>> pq;  // 小さい順
pq.push(n)  // while(!pq.empty()){cout<<pq.top(); pq.pop();}  // O(logN)*/

// ***** dsu ******************************
/*dsu d(n);
if(!d.same(a,b)) d.merge(a,b);
vvi g=d.groups();
cout << g.size();*/

// ***** 最大公約数 ************************
ll gcd(ll x, ll y){while(y>0){ll r=x%y; x=y; y=r;} return x;}

// ***** 素数判定 **************************
bool is_prime(ll N){
 if(N==1) return 0;
 for(ll i=2; i*i<=N; i++){if(N%i==0) return 0;}
 return 1;
}

// ***** エラトステネスのふるい **************
/*ll n;
vb prime(n+1,1);
void hurui(){
  prime[0]=0; prime[1]=0;
  for(ll i=2; i<=n; i++) if(prime[i]) for(ll j=2*i; j<=n; j+=i) prime[j]=0;
}*/

// ***** 累乗、逆元 ************************
//using mint = static_modint<107*109>;
/*int main(){
  modint::set_mod(ppp);
  xxx.pow(nnn);
}*/
ll modPow(ll x, ll n, ll p){
  if(n== 1) return x;
  if(n%2) return (x*modPow(x,n-1,p))%p;
  ll t=modPow(x,n/2,p); return (t*t)%p;
}
ll modInv(ll x, ll p){return modPow(x,p-2,p);}

// ***** 階乗、階乗の逆 *********************
const ll MAX = 123456;
vl fac(MAX), finv(MAX), inv(MAX); // i!, (i!)^(-1), i^(-1)
void COMinit(ll p){
  fac[0]=fac[1]=1; finv[0]=finv[1]=1; inv[1]=1;
  for(ll i=2; i<MAX; i++){fac[i] = (fac[i-1]*i)%p; inv[i] = p-(inv[p%i]*(p/i))%p; finv[i] = (finv[i-1]*inv[i])%p;}
}
// ***** 二項係数 **************************
ll COM(ll n, ll k, ll p){if(n<0 || k<0 || n<k) return 0; return ((fac[n]*finv[k])%p*finv[n-k])%p;}

// ***** max, minの更新 ********************
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b; return 1;} return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b; return 1;} return 0;}

// ***** 上下左右（前4項）＋斜めに移動 *******
const int dx[] = {1, 0,-1, 0, 1, -1, 1, -1};
const int dy[] = {0,-1, 0, 1, 1, 1, -1, -1};

// ***** 2分探索 ***************************
  // f(0)=1, f(L)=0
  /*int m=0,M=L;
  while(M-m>1){
    int a=m+(M-m)/2;
    if(f(a)) m=a;
    else M=a;
  }*/
  // f[m]=1, f[M]=0, m+1=M

// ***** n!通り探索 ************************
/*  vi v={};
  do{
    vi w(0);
    for(int x:v) w.push_back(x);
  }while(next_permutation(v.begin(), v.end()));*/

// ***** DFS ******************************
/*vvi G;
vb seen;
void dfs(int v){
  seen[v]=1;
  // 行きがけ
  for(int w:G[v]){
    if(seen[w]) continue;
    dfs(w);
    // 帰りがけ
  }
}
int main(){
  rep(i,M){
    int a,b;
    cin >> a>>b;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  G.assign(N,vi(0));
  seen.assign(N,0);
  dfs(G,s);
}*/

// ***** BFS ******************************
/*  vi dist(N,-1);
  queue<int> que;
  dist[0]=0;
  que.push(0);
  while(!que.empty()){
    int v=que.front();
    que.pop();
    for(int w:G[v]){
      if(dist[w]!=-1) continue;
      dist[w]=dist[v]+1;
      que.push(w);
    }
  }*/

// ***** 転倒数 ***************************
/*ll merge_cnt(vll &a){
  int n=a.size();
  if(n<=1) return 0;
  vll b(a.begin(),a.begin()+n/2),c(a.begin()+n/2,a.end());
  ll cnt = 0;
  cnt+=merge_cnt(b);cnt+=merge_cnt(c);
  int ai=0,bi=0,ci=0;
  while(ai<n){
    if(bi<(int)b.size() && (ci==(int)c.size() || b[bi]<=c[ci])) a[ai++]=b[bi++];
    else{cnt+=n/2-bi; a[ai++]=c[ci++];}
  }
  return cnt;
}*/

// ***** インタラクティブな問題 *************
/*  while(){
    cout << ? << endl;
    cout << flush;
    cin >> ?; if(?);
  }*/




int main() {
  int N,M;
  cin >> N>>M;
  vi L(M),R(M);
  rep(i,M) cin >> L[i]>>R[i];
  
  vi dcnt(N+2,0);
  rep(i,M){
    dcnt[L[i]]++;
    dcnt[R[i]+1]--;
  }
  vi cnt(N+2,0);
  rep1(i,N+1) cnt[i]=cnt[i-1]+dcnt[i];
  
  int ans=cnt[1];
  rep1(i,N) chmin(ans,cnt[i]);
  
  cout << ans << endl;
  
  return 0;
}

提出情報

ジャッジ結果