Submission #00207

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
//header{{{
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define Fixed fixed << setprecision(12)
#define int int_fast64_t
using pii = pair<int,int>;
constexpr int INF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod1 = 1e9+7;
constexpr int mod2 = 998244353;
template <class Func>
class FixPoint : Func {
public:
explicit constexpr FixPoint(Func&& f) noexcept : Func(forward<Func>(f)) {}
template <class... Args>
constexpr decltype(auto) operator()(Args&&... args) const {
return Func::operator()(*this, std::forward<Args>(args)...);
}
};
template <class Func>
static inline constexpr decltype(auto) makeFixPoint(Func&& f) noexcept {
return FixPoint<Func>{forward<Func>(f)};
}
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;
template <class A, class B> using umap = unordered_map<A,B>;
template <class T> using Set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class K, class V> using Umap = gp_hash_table<K, V>;
using Trie = trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update>;
inline int square(int a){ return a * a;}
inline int updiv(int a,int b){ return (a + b - 1) / b; }
constexpr int dx[] = {1,0,-1,0,1,1,-1,-1};
constexpr int dy[] = {0,-1,0,1,1,-1,-1,1};
//}}}
signed main(){
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
cout.setf(ios_base::fixed);
cout.precision(10);
int n, q;
string s;
cin >> n >> q >> s;
vector<int> div;
for(int i = 1; i * i <= n; ++i){
if(n % i == 0){
div.emplace_back(i);
if(i * i != n){
div.emplace_back(n / i);
}
}
}
sort(all(div));
int siz = div.size();
vector<vector<vector<int> > > v(siz);
vector<int> ok(siz);
rep(i,siz){
v[i].resize(div[i], vector<int>(26));
}
vector<int> str(n);
rep(i,n){
str[i] = s[i] - 'a';
}
rep(i,siz){ //div[i]ずつに分割
rep(j,div[i]){
for(int k = j; k < n; k += div[i]){
v[i][j][str[k]]++;
}
if(v[i][j][str[j]] == n / div[i]){
ok[i]++;
}
}
}
rep(loop,q){
int p;
char c;
cin >> p >> c;
--p;
c = c - 'a';
if(str[p] != c){
rep(i,siz){
int pos = p % div[i];
if(v[i][pos][str[p]] == n / div[i]){
ok[i]--;
}
v[i][pos][str[p]]--;
v[i][pos][c]++;
if(v[i][pos][c] == n / div[i]){
ok[i]++;
}
}
}
str[p] = c;
rep(i,siz){
if(ok[i] == div[i]){
cout << div[i] << '\n';
break;
}
}
}
return 0;
}

ステータス

項目 データ
問題 0011 - イワシロの祈り
ユーザー名 虚無
投稿日時 2020-08-17 11:58:17
言語 C++17
状態 Accepted
得点 12
ソースコード長 3671 Byte
最大実行時間 419 ms
最大メモリ使用量 93108 KB

セット

セット 得点 Cases
1 ALL 12 / 12 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1 AC 29 ms 604 KB
1
in2 AC 22 ms 788 KB
1
in3 AC 20 ms 6264 KB
1
in4 AC 17 ms 8576 KB
1
in5 AC 21 ms 8524 KB
1
in6 AC 17 ms 8604 KB
1
in7 AC 17 ms 8548 KB
1
in8 AC 22 ms 8492 KB
1
in9 AC 16 ms 8564 KB
1
in10 AC 21 ms 556 KB
1
in11 AC 17 ms 628 KB
1
in12 AC 17 ms 448 KB
1
in13 AC 23 ms 524 KB
1
in14 AC 21 ms 604 KB
1
in15 AC 30 ms 6584 KB
1
in16 AC 88 ms 61236 KB
1
in17 AC 21 ms 680 KB
1
in18 AC 20 ms 888 KB
1
in19 AC 21 ms 1416 KB
1
in20 AC 19 ms 1380 KB
1
in21 AC 273 ms 62060 KB
1
in22 AC 282 ms 62696 KB
1
in23 AC 281 ms 63452 KB
1
in24 AC 157 ms 64208 KB
1
in25 AC 163 ms 64716 KB
1
in26 AC 68 ms 29888 KB
1
in27 AC 25 ms 7420 KB
1
in28 AC 95 ms 11516 KB
1
in29 AC 93 ms 12152 KB
1
in30 AC 419 ms 91336 KB
1
in31 AC 391 ms 91800 KB
1
in32 AC 417 ms 92516 KB
1
in33 AC 405 ms 93108 KB
1