Submission #545961

#	Time	Username	Problem	Language	Result	Execution time	Memory
545961		ivan_tudor	Misspelling (JOI22_misspelling)	C++14	0 / 100	1018 ms	642692 KiB

misspelling

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
const int N = 500005;
const int MOD = 1e9 + 7;
const int SIGMA = 26;
void add(int &x, long long y){
  y%=MOD;
  x += y;
  if(x >= MOD)
    x-=MOD;
  if(x<0)
    x+=MOD;
}
struct dphelper{
  int nways;
  int lateless;
  int latebig;
};
int lessthan[N];
int bigthan[N];
dphelper dp[N][SIGMA + 1][2][2];
const int INF = -1e9;

int fbg[N], fls[N];
void compute(int n){
  vector<int> st;
  st.push_back(n + 1);
  lessthan[n + 1] = n + 1;
  for(int i = n; i >=1; i--){
    while(st.size() && lessthan[i] > lessthan[st.back()])
      st.pop_back();
    fls[i] = st.back();
    st.push_back(i);
  }
  st.clear();
  st.push_back(n + 1);
  bigthan[n + 1] = n + 1;
  for(int i = n; i >=1; i--){
    while(st.size() && bigthan[i] > bigthan[st.back()])
      st.pop_back();
    fbg[i] = st.back();
    st.push_back(i);
  }
}
int main()
{
  int n, m;
  cin>>n>>m;
  for(int i = 1; i<=m; i++){
    int x, y;
    cin>>x>>y;
    if(x < y)
      bigthan[x] = max(bigthan[x], y);
    if(x > y)
      lessthan[y] = max(lessthan[y], x);;
  }
  compute(n);
  for(int i = 0; i<=n; i++){
    for(int let = 0; let<=SIGMA; let++){
      for(int tp1 = 0; tp1<=1; tp1++)
        for(int tp2 = 0; tp2<=1; tp2++)
      dp[i][let][tp1][tp2] = {0, INF, INF};
    }
  }
  for(int let = 1; let<=SIGMA; let++){
    int ls = 0, bg = 0;
    if(lessthan[1])
      ls = 1;
    if(bigthan[1])
      bg = 1;
    if(ls == bg && ls == 1){
      int lless, lbig;
      lless = lessthan[1];
      lbig = bigthan[1];
      int mn = min(lless, lbig);
      int futurels = 0, futurebg = 0;
      if(lless - mn> 0)
        futurels = 1;
      if(lbig  - mn> 0)
        futurebg = 1;
      if(futurels == 0 && futurebg == 0)
        mn = min(mn, min(fls[1], fbg[1]));
      else if(futurels == 0)
        mn = min(mn, fls[1]);
      else
        mn = min(mn, fbg[1]);
      add(dp[mn][let][futurels][futurebg].nways, 1); /// o sa se pastreze restul restrictiilor
      if(futurels){
        dp[mn][let][futurels][futurebg].lateless = max(dp[mn][let][futurels][futurebg].lateless, lless);
      }
      if(futurebg){
        dp[mn][let][futurels][futurebg].latebig = max(dp[mn][let][futurels][futurebg].latebig, lbig);
      }
    }
    else{
      dp[1][let][ls][bg].nways = 1;
      if(ls)
        dp[1][let][ls][bg].lateless = lessthan[1];
      if(bg)
        dp[1][let][ls][bg].latebig = bigthan[1];
    }
  }


  for(int i = 2; i<=n; i++){
    /// propag pe i - 1, dupa pun restrictiile pt poz i noi si le scot pe cele vechi
    /// propag fara restrictii
    int total_sum = 0;
    for(int let = 1; let <= SIGMA; let++)
      add(total_sum, dp[i - 1][let][0][0].nways);
    for(int let = 1; let <= SIGMA; let++){
      add(dp[i][let][0][0].nways, total_sum);
    }
    total_sum = 0;
    for(int let = SIGMA; let>= 1; let--){
      add(dp[i][let][0][0].nways, total_sum); /// am pus mai mic si am scapat de restrictii
      add(total_sum, dp[i - 1][let][1][0].nways);
      if(dp[i - 1][let][1][0].lateless == i)
        add(dp[i][let][0][0].nways, dp[i - 1][let][1][0].nways);
      else{
        add(dp[i][let][1][0].nways, dp[i -1][let][1][0].nways);

        dp[i][let][1][0].lateless = max(dp[i][let][1][0].lateless, dp[i -1][let][1][0].lateless);

      }
    }

    total_sum = 0;
    for(int let = 1; let<= SIGMA; let++){
      add(dp[i][let][0][0].nways, total_sum); /// am pus mai mare si am scapat de restrictii
      add(total_sum, dp[i - 1][let][0][1].nways);
      if(dp[i - 1][let][0][1].latebig == i)
        add(dp[i][let][0][0].nways, dp[i - 1][let][0][1].nways);
      else{
        add(dp[i][let][0][1].nways, dp[i -1][let][0][1].nways);

        dp[i][let][0][1].latebig = max(dp[i][let][0][1].latebig, dp[i -1][let][0][1].latebig);
      }
    }

    /// bag restrictiile noi
    for(int let = 1; let <=SIGMA; let++){
      assert(dp[i][let][1][1].nways == 0);
      for(int ls = 1; ls >=0; ls--){
        for(int bg = 1; bg >=0; bg--){
          int newls = ls, newbg = bg;
          if(lessthan[i] > 0)
            newls = 1;
          if(bigthan[i] > 0)
            newbg = 1;
          if(newls == 1 && newbg == 1){
            int lless, lbig;
            lless = dp[i][let][ls][bg].lateless;
            lbig = dp[i][let][ls][bg].latebig;

            lless = max(lless, lessthan[i]);
            lbig = max(lbig, bigthan[i]);
            if(dp[i][let][ls][bg].nways){
              int mn = min(lless, lbig);
              int futurels = 0, futurebg = 0;
              if(lless - mn> 0)
                futurels = 1;
              if(lbig  - mn> 0)
                futurebg = 1;
              if(futurels == 0 && futurebg == 0)
                mn = min(mn, min(fls[i], fbg[i]));
              else if(futurels == 0)
                mn = min(mn, fls[i]);
              else
                mn = min(mn, fbg[i]);
              add(dp[mn][let][futurels][futurebg].nways, dp[i][let][ls][bg].nways); /// o sa se pastreze restul restrictiilor
              if(futurels){
                dp[mn][let][futurels][futurebg].lateless = max(dp[mn][let][futurels][futurebg].lateless, lless);
              }
              if(futurebg){
                dp[mn][let][futurels][futurebg].latebig = max(dp[mn][let][futurels][futurebg].latebig, lbig);
              }
            }
            dp[i][let][ls][bg] = {0, INF, INF};
          }
          else{
            if(lessthan[i] > 0)
              dp[i][let][newls][newbg].lateless = max(dp[i][let][newls][newbg].lateless, lessthan[i]);
            if(bigthan[i] > 0)
              dp[i][let][newls][newbg].latebig = max(dp[i][let][newls][newbg].latebig, bigthan[i]);
            if((pair<int, int>){ls, bg} != (pair<int, int>){newls, newbg}){ /// cazul din 0 0 in cv ce nu e 1 0 sau 0 1
              add(dp[i][let][newls][newbg].nways, dp[i][let][ls][bg].nways);
              dp[i][let][ls][bg] = {0, INF, INF};
            }
          }
        }
      }

    }

  }
  int ans = 0;
  for(int let = 1; let<=SIGMA; let++){
    add(ans, dp[n][let][0][0].nways);
    add(ans, dp[n][let][0][1].nways);
    add(ans, dp[n][let][1][0].nways);
  }
  cout<<ans;
  return 0;
}

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