CSES - Datatähti 2025 alku - Results
Submission details
Task:Niitty
Sender:vgtcross
Submission time:2024-10-28 02:54:27 +0200
Language:C++ (C++20)
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED4
#2ACCEPTED6
#3ACCEPTED10
#4ACCEPTED13
#5ACCEPTED25
#6ACCEPTED42
Test results
testverdicttimegroup
#1ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#2ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#3ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#4ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#5ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#6ACCEPTED0.00 s2, 3, 4, 5, 6details
#7ACCEPTED0.00 s2, 3, 4, 5, 6details
#8ACCEPTED0.00 s2, 3, 4, 5, 6details
#9ACCEPTED0.00 s2, 3, 4, 5, 6details
#10ACCEPTED0.01 s3, 4, 5, 6details
#11ACCEPTED0.01 s3, 4, 5, 6details
#12ACCEPTED0.00 s3, 4, 5, 6details
#13ACCEPTED0.00 s3, 4, 5, 6details
#14ACCEPTED0.01 s4, 5, 6details
#15ACCEPTED0.01 s4, 5, 6details
#16ACCEPTED0.01 s4, 5, 6details
#17ACCEPTED0.01 s4, 5, 6details
#18ACCEPTED0.05 s5, 6details
#19ACCEPTED0.07 s5, 6details
#20ACCEPTED0.05 s5, 6details
#21ACCEPTED0.04 s5, 6details
#22ACCEPTED0.77 s6details
#23ACCEPTED0.95 s6details
#24ACCEPTED0.77 s6details
#25ACCEPTED0.74 s6details

Code

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define MODE 1
#if MODE
#define debug(x) cout << #x << ": " << (x) << endl
#define log(x) cout << (x) << endl
#define test(x) x
#else
#define debug(x)
#define log(x)
#define test(x)
#endif
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fi first
#define se second
#define X real()
#define Y imag()
using namespace std;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using P = complex<ll>;
template<typename S, typename T = S> void chmin(S &s, T t) {s = s < t ? s : t;}
template<typename S, typename T = S> void chmax(S &s, T t) {s = s > t ? s : t;}
const ll M = 1000000007; // 998244353
const int N = 505;
template<typename T>
struct orstack {
vector<pair<T, T>> st;
T def = T{};
orstack() {}
orstack(int n) : def(0) {
st.reserve(n);
}
size_t size() {
return st.size();
}
T getor() {
return st.size() ? st.back().se : def;
}
void push(T v) {
st.push_back({v, v | getor()});
}
void pop() {
st.pop_back();
}
T top() {
return st.back().fi;
}
};
template<typename T>
struct orqueue {
orstack<T> in, out;
orqueue(int n) {
in = orstack<T>(n);
out = orstack<T>(n);
}
size_t size() {
return in.size() + out.size();
}
T getor() {
return in.getor() | out.getor();
}
void push(T v) {
in.push(v);
}
void balance() {
if (!out.size()) {
while (in.size()) {
out.push(in.top());
in.pop();
}
}
}
void pop() {
balance();
out.pop();
}
T front() {
balance();
return out.top();
}
};
int mask[N][N];
void solve() {
int n;
cin >> n;
vector<string> g(n);
for (auto &s : g) cin >> s;
int w = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
w |= 1 << (g[i][j] - 'A');
}
}
ll ans = 0;
for (int l = 0; l < n; ++l) {
for (int r = l; r < n; ++r) {
orqueue<int> q(n);
for (int i = 0; i < n; ++i) {
if (l == r) mask[i][r] = 1 << (g[i][r] - 'A');
else mask[i][r] = mask[i][r-1] | 1 << (g[i][r] - 'A');
q.push(mask[i][r]);
while (q.getor() == w) q.pop();
ans += i+1 - q.size();
}
}
}
cout << ans << '\n';
}
int main() {
cin.tie(0) -> sync_with_stdio(0);
int t = 1;
if (t == 0) cin >> t;
while (t--) solve();
return 0;
}

Test details

Test 1

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
10
TNCTNPNTPC
NPPNTNTPTP
NTNTTCNTCT
NPCPNPPNTT
...

correct output
2035

user output
2035

Test 2

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
10
NFWQLWNWYS
DZOQJVXFPJ
CNHXPXMCQD
QRTBVNLTQC
...

correct output
9

user output
9

Test 3

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
10
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
...

correct output
3025

user output
3025

Test 4

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
10
FFFFFFFFFF
FFFFFCFFFF
FFFFFFJFFF
FFFFFFFFFF
...

correct output
12

user output
12

Test 5

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
1
X

correct output
1

user output
1

Test 6

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
20
BBCBUBOUOBBCUUBBCOUO
BOUCOOCUBCOOOCOBOCUO
UCCUUUOBCOCBCBUBUCOO
BUOBUCUCUOOBCOOUBUOO
...

correct output
38724

user output
38724

Test 7

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
20
CBGLSHGZHYZDWBNDBJUG
SMUXOJQYPXZDTMJUIWOJ
XIDSTNBGHKRKOVUVMINB
MTQGCFRUHQKALXRNCQGS
...

correct output
8334

user output
8334

Test 8

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
20
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
...

correct output
44100

user output
44100

Test 9

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
20
AAAAAAAAXAAAAAAAAAAA
AAAWAAAAAAAAAAAAAOAA
AAAAAAAAAAAAAAAAAPAA
AAAAAAAAKAAAAAAAAAAZ
...

correct output
18

user output
18

Test 10

Group: 3, 4, 5, 6

Verdict: ACCEPTED

input
50
GRGREEEGREGXRXXEGXXREXGRRRGRRR...

correct output
1584665

user output
1584665

Test 11

Group: 3, 4, 5, 6

Verdict: ACCEPTED

input
50
AITIISJUHCCRZNKSDCNQKYSQRINFWJ...

correct output
1077746

user output
1077746

Test 12

Group: 3, 4, 5, 6

Verdict: ACCEPTED

input
50
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

correct output
1625625

user output
1625625

Test 13

Group: 3, 4, 5, 6

Verdict: ACCEPTED

input
50
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFF...

correct output
1680

user output
1680

Test 14

Group: 4, 5, 6

Verdict: ACCEPTED

input
100
NNCMDCDDCCNNNDNCMMNCDCDCCDCDNM...

correct output
25325366

user output
25325366

Test 15

Group: 4, 5, 6

Verdict: ACCEPTED

input
100
LIMQQIHASECROEVILNVULGWZJPPKOG...

correct output
22342463

user output
22342463

Test 16

Group: 4, 5, 6

Verdict: ACCEPTED

input
100
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTT...

correct output
25502500

user output
25502500

Test 17

Group: 4, 5, 6

Verdict: ACCEPTED

input
100
QXQQQQQQQQQQQQQQQQQQQQQQQQQQQQ...

correct output
25650

user output
25650

Test 18

Group: 5, 6

Verdict: ACCEPTED

input
200
NAANANMMKNKKAKMKMAKNKMNKMMNNAA...

correct output
403292767

user output
403292767

Test 19

Group: 5, 6

Verdict: ACCEPTED

input
200
OMYWATTLURKQPTKEFMGGYAOONXWVSC...

correct output
388111321

user output
388111321

Test 20

Group: 5, 6

Verdict: ACCEPTED

input
200
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCC...

correct output
404010000

user output
404010000

Test 21

Group: 5, 6

Verdict: ACCEPTED

input
200
LLLLLLLLLLLLLLLLLHLLLLLLLLLLLL...

correct output
14159445

user output
14159445

Test 22

Group: 6

Verdict: ACCEPTED

input
500
VVHWVUHVHUWWWVUUUWVUUHUUWHWUVW...

correct output
15683003812

user output
15683003812

Test 23

Group: 6

Verdict: ACCEPTED

input
500
OIMZGEQSBMBDSDXSWRFNKSGFEBBTJE...

correct output
15575906951

user output
15575906951

Test 24

Group: 6

Verdict: ACCEPTED

input
500
IIIIIIIIIIIIIIIIIIIIIIIIIIIIII...

correct output
15687562500

user output
15687562500

Test 25

Group: 6

Verdict: ACCEPTED

input
500
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWW...

correct output
3058970930

user output
3058970930