제출 #546143

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
546143		ivan_tudor	Misspelling (JOI22_misspelling)	C++14	60 / 100	4123 ms	861872 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;
}
const int INF = -1e9;
struct aintstr{
  vector<int> aint;
  vector<int> lazy;
  const static int SZ = N;
  aintstr(): aint(4*N + 1, 0), lazy(4*N + 1, INF){
  }
  void propag(int nod, int l, int r){
    if(lazy[nod] == INF)
      return;
    aint[nod] = 1LL * (r - l + 1) * lazy[nod] % MOD;
    if(l != r){
      lazy[2*nod] = lazy[2*nod + 1] = lazy[nod];
    }
    lazy[nod] = INF;
  }
  void update(int lpoz, int rpoz, int val, int nod = 1, int l = 1, int r = SZ){
    propag(nod, l, r);
    if(rpoz < l || lpoz >r)
      return;
    if(lpoz <= l && r <= rpoz){
      lazy[nod] = val;
      propag(nod, l, r);
      return;
    }
    int mid = (l +r)/2;
    update(lpoz, rpoz, val, 2*nod, l, mid);
    update(lpoz, rpoz, val, 2*nod + 1, mid + 1, r);
    aint[nod] = (aint[2*nod] + aint[2*nod + 1])%MOD;
  }
  int get_sum(){
    propag(1, 1, SZ);
    return aint[1];
  }
};

int lessthan[N];
int bigthan[N];

int start[N][SIGMA + 1];
aintstr dp[SIGMA + 1][2]; /// 0 merge in jos, 1 merge in sus


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);;
  }
  for(int i = 1; i<=SIGMA; i++){
    start[n][i] = 1;
  }
  for(int i = n - 1; i>=1; i--){
    int total_sum = 0;
    for(int let = 1; let<=SIGMA; let++){
      dp[let][0].update(i + 1, i + 1, total_sum);
      add(total_sum, start[i + 1][let]);
    }
    total_sum = 0;
    for(int let = SIGMA; let>=1; let--){
      dp[let][1].update(i + 1, i + 1, total_sum);
      add(total_sum, start[i + 1][let]);
    }
    for(int let = 1; let<=SIGMA; let++){
      if(bigthan[i]){
        dp[let][0].update(i + 1, bigthan[i], 0);
      }
      if(lessthan[i]){
        dp[let][1].update(i + 1, lessthan[i], 0);
      }
      start[i][let] = 1;
      add(start[i][let], dp[let][0].get_sum());
      add(start[i][let], dp[let][1].get_sum());
    }
  }
  int ans = 0;
  for(int i = 1; i<=SIGMA; i++)
    add(ans, start[1][i]);
  cout<<ans;
  return 0;
}

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