oj.uz

Submission #546148

# Submission time Handle Problem Language Result Execution time Memory
546148 2022-04-06T14:05:51 Z ivan_tudor Misspelling (JOI22_misspelling) C++14
60 / 100
 4000 ms 865868 KB 
#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 = -1;
struct aintstr{
  vector<int> aint;
  vector<int> lazy;
  aintstr(): aint(4*N + 1, 0), lazy(4*N + 1, INF){
  }
  inline void propag(int nod, int l, int r){
    if(lazy[nod] == INF)
      return;
    aint[nod] = (r - l + 1) * lazy[nod];
    if(l != r){
      lazy[2*nod] = lazy[2*nod + 1] = lazy[nod];
    }
    lazy[nod] = INF;
  }
  inline void update(int lpoz, int rpoz, int val, int nod = 1, int l = 1, int r = N){
    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];
    if(aint[nod]>=MOD)
      aint[nod]-=MOD;
  }
  int get_sum(){
    propag(1, 1, N);
    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()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 846020 KB Output is correct
2 Correct 338 ms 846120 KB Output is correct
3 Correct 332 ms 846068 KB Output is correct
4 Correct 293 ms 846096 KB Output is correct
5 Correct 326 ms 846096 KB Output is correct
6 Correct 330 ms 846012 KB Output is correct
7 Correct 298 ms 846040 KB Output is correct
8 Correct 337 ms 846068 KB Output is correct
9 Correct 338 ms 846024 KB Output is correct
10 Correct 311 ms 846232 KB Output is correct
11 Correct 317 ms 846092 KB Output is correct
12 Correct 304 ms 846116 KB Output is correct
13 Correct 312 ms 846012 KB Output is correct
14 Correct 319 ms 846252 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 846020 KB Output is correct
2 Correct 338 ms 846120 KB Output is correct
3 Correct 332 ms 846068 KB Output is correct
4 Correct 293 ms 846096 KB Output is correct
5 Correct 326 ms 846096 KB Output is correct
6 Correct 330 ms 846012 KB Output is correct
7 Correct 298 ms 846040 KB Output is correct
8 Correct 337 ms 846068 KB Output is correct
9 Correct 338 ms 846024 KB Output is correct
10 Correct 311 ms 846232 KB Output is correct
11 Correct 317 ms 846092 KB Output is correct
12 Correct 304 ms 846116 KB Output is correct
13 Correct 312 ms 846012 KB Output is correct
14 Correct 319 ms 846252 KB Output is correct
15 Correct 301 ms 846028 KB Output is correct
16 Correct 367 ms 846028 KB Output is correct
17 Correct 300 ms 846028 KB Output is correct
18 Correct 319 ms 846156 KB Output is correct
19 Correct 312 ms 846116 KB Output is correct
20 Correct 317 ms 846028 KB Output is correct
21 Correct 306 ms 846036 KB Output is correct
22 Correct 306 ms 846136 KB Output is correct
23 Correct 315 ms 846216 KB Output is correct
24 Correct 303 ms 846028 KB Output is correct
25 Correct 310 ms 846060 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 846156 KB Output is correct
2 Correct 299 ms 846100 KB Output is correct
3 Correct 316 ms 846188 KB Output is correct
4 Correct 324 ms 846040 KB Output is correct
5 Execution timed out 4122 ms 865868 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 846020 KB Output is correct
2 Correct 338 ms 846120 KB Output is correct
3 Correct 332 ms 846068 KB Output is correct
4 Correct 293 ms 846096 KB Output is correct
5 Correct 326 ms 846096 KB Output is correct
6 Correct 330 ms 846012 KB Output is correct
7 Correct 298 ms 846040 KB Output is correct
8 Correct 337 ms 846068 KB Output is correct
9 Correct 338 ms 846024 KB Output is correct
10 Correct 311 ms 846232 KB Output is correct
11 Correct 317 ms 846092 KB Output is correct
12 Correct 304 ms 846116 KB Output is correct
13 Correct 312 ms 846012 KB Output is correct
14 Correct 319 ms 846252 KB Output is correct
15 Correct 301 ms 846028 KB Output is correct
16 Correct 367 ms 846028 KB Output is correct
17 Correct 300 ms 846028 KB Output is correct
18 Correct 319 ms 846156 KB Output is correct
19 Correct 312 ms 846116 KB Output is correct
20 Correct 317 ms 846028 KB Output is correct
21 Correct 306 ms 846036 KB Output is correct
22 Correct 306 ms 846136 KB Output is correct
23 Correct 315 ms 846216 KB Output is correct
24 Correct 303 ms 846028 KB Output is correct
25 Correct 310 ms 846060 KB Output is correct
26 Correct 818 ms 848336 KB Output is correct
27 Correct 824 ms 848516 KB Output is correct
28 Correct 856 ms 848312 KB Output is correct
29 Correct 932 ms 848356 KB Output is correct
30 Correct 957 ms 848332 KB Output is correct
31 Correct 1185 ms 848292 KB Output is correct
32 Correct 963 ms 848428 KB Output is correct
33 Correct 906 ms 848312 KB Output is correct
34 Correct 940 ms 848332 KB Output is correct
35 Correct 1432 ms 848456 KB Output is correct
36 Correct 705 ms 848188 KB Output is correct
37 Correct 881 ms 848324 KB Output is correct
38 Correct 882 ms 848288 KB Output is correct
39 Correct 788 ms 848360 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 846020 KB Output is correct
2 Correct 338 ms 846120 KB Output is correct
3 Correct 332 ms 846068 KB Output is correct
4 Correct 293 ms 846096 KB Output is correct
5 Correct 326 ms 846096 KB Output is correct
6 Correct 330 ms 846012 KB Output is correct
7 Correct 298 ms 846040 KB Output is correct
8 Correct 337 ms 846068 KB Output is correct
9 Correct 338 ms 846024 KB Output is correct
10 Correct 311 ms 846232 KB Output is correct
11 Correct 317 ms 846092 KB Output is correct
12 Correct 304 ms 846116 KB Output is correct
13 Correct 312 ms 846012 KB Output is correct
14 Correct 319 ms 846252 KB Output is correct
15 Correct 301 ms 846028 KB Output is correct
16 Correct 367 ms 846028 KB Output is correct
17 Correct 300 ms 846028 KB Output is correct
18 Correct 319 ms 846156 KB Output is correct
19 Correct 312 ms 846116 KB Output is correct
20 Correct 317 ms 846028 KB Output is correct
21 Correct 306 ms 846036 KB Output is correct
22 Correct 306 ms 846136 KB Output is correct
23 Correct 315 ms 846216 KB Output is correct
24 Correct 303 ms 846028 KB Output is correct
25 Correct 310 ms 846060 KB Output is correct
26 Correct 309 ms 846156 KB Output is correct
27 Correct 299 ms 846100 KB Output is correct
28 Correct 316 ms 846188 KB Output is correct
29 Correct 324 ms 846040 KB Output is correct
30 Execution timed out 4122 ms 865868 KB Time limit exceeded
31 Halted 0 ms 0 KB -