Submission #1204233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204233		mychecksedad	Misspelling (JOI22_misspelling)	C++20	100 / 100	412 ms	246708 KiB

misspelling

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;


int n, m;
ll pref[K][2], suf[K][2], dp[N][K];
vector<array<int, 3>> v;

void add(int j, int coef, int id){
  ll sum = 0;
  for(int i = 0; i < 26; ++i){
    sum += dp[j][i];
    pref[i][id] += sum * coef;
  }
  sum = 0;
  for(int i = 25; i >= 0; --i){
    sum += dp[j][i];
    suf[i][id] += sum * coef;
  }
}

void solve(){
  cin >> n >> m;
  for(int i = 1; i <= m; ++i){
    int x, y; cin >> x >> y;
    if(x <= y){
      v.pb({x, y, 0});
    }else{
      v.pb({y, x, 1});
    }
  }
  sort(all(v));
  int ptr = m - 1;
  multiset<int> A, B; // 0, 1
  
  for(int j = 0; j < 26; ++j) pref[j][0] = pref[j][1] = suf[j][0] = suf[j][1] = 0;
  for(int j = 0; j < 26; ++j) dp[n][j] = 1;
  add(n, 1, 0); 
  add(n, 1, 1); 
  A.insert(n);
  B.insert(n);

  for(int i = n - 1; i >= 1; --i){
    
    for(int j = 0; j < 26; ++j) dp[i][j] = 0;
    
    while(ptr >= 0 && v[ptr][0] >= i){
      int r = v[ptr][1];
      int tp = v[ptr][2];
      if(tp == 0){
        while(B.size() && (*B.begin()) <= r){
          add(*B.begin(), -1, 1);
          B.erase(B.begin());
        }
      }else{
        while(A.size() && (*A.begin()) <= r){
          add(*A.begin(), -1, 0);
          A.erase(A.begin());
        }
      }
      --ptr;
    }

    for(int j = 0; j < 26; ++j){
      dp[i][j] = 1;
      if(j > 0){
        dp[i][j] += pref[j - 1][0];
      }
      if(j < 25){
        dp[i][j] += suf[j + 1][1];
      }
      dp[i][j] %= MOD;
    }


    add(i, 1, 0);
    add(i, 1, 1);

    if(i == 1){
      ll ans = 0;
      for(int j = 0; j < 26; ++j) ans += dp[i][j];
      cout << ans % MOD;
    }
    A.insert(i);
    B.insert(i);
    // for(int j = 0; j < 26; ++j) cout << dp[i][j] << ' ';
    // en;
  }
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
    en;
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

• Subtask 1: 8 / 8
• Subtask 2: 20 / 20
• Subtask 3: 29 / 29
• Subtask 4: 32 / 32
• Subtask 5: 11 / 11