Submission #47878221

---

Source Code Expand

#include<bits/stdc++.h>
#define ll long long
#define db double
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define FR first
#define SE second
using namespace std;
inline int read() {
  int x = 0; bool op = false;
  char c = getchar();
  while(!isdigit(c))op |= (c == '-'), c = getchar();
  while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  return op ? -x : x;
}
const int N = 5e5 + 10;
const int P = 998244353;
void add(int &a, int b) {a += b; a >= P ? a -= P : 0;}
void sub(int &a, int b) {a -= b; a < 0 ? a += P : 0;}
int n;
int nxt[N], sum[N], a[N], b[N], f[N], d[N];
int calc(int l, int r) {
  for(int i = l; i <= r; i++)a[i - l + 1] = a[i], b[i - l + 1] = b[i];
  int n = r - l + 1;
  // printf("%d\n", n);
  for(int i = 0; i <= n; i++)d[i] = f[i] = sum[i] = 0;
  int ans = 1;
  for(int i = 1; i <= n; i++) {
    int s1 = 0, s2 = 1;
    add(d[i], d[i - 1]); f[i] = d[i];
    int pos = upper_bound(b + 1, b + 1 + n, a[i]) - b + 1;
    pos = min(pos, i);
    sum[i] = (sum[i - 1] + f[i]) % P;
    s1 = (sum[i - 1] - sum[pos - 1] + P) % P;
    s2 = (sum[pos - 1] + 1) % P;
    pos = lower_bound(a + 1, a + 1 + n, b[i]) - a - 1;
    add(d[i + 1], (s1 + s2) % P); sub(d[pos + 1], (s1 + s2) % P);
    if(pos + 1 <= n)add(d[pos + 1], s1);
    add(ans, s1); add(ans, f[i]);
    // printf("f:%d %d %d %d\n", i, f[i], s1, s2);
  }
  // printf("ans:%d\n", ans);
  return ans;
}
int main() {
  n = read();
  for(int i = 1; i <= n; i++)a[i] = read(), b[i] = read();
  int ans = 1;
  for(int i = 1; i <= n; i++) {
    int k = i;
    while(k < n && a[k + 1] <= b[k])k++;
    ans = 1ll * ans * calc(i, k) % P;
    i = k;
  }
  printf("%d\n", ans);
  return 0;
}

Submission Info

Judge Result