CSES - Datatähti 2025 alku - Results
Submission details
Task:Niitty
Sender:aatukaj
Submission time:2024-10-28 18:16:40 +0200
Language:C++ (C++20)
Status:READY
Result:58
Feedback
groupverdictscore
#1ACCEPTED4
#2ACCEPTED6
#3ACCEPTED10
#4ACCEPTED13
#5ACCEPTED25
#60
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.01 s3, 4, 5, 6details
#13ACCEPTED0.01 s3, 4, 5, 6details
#14ACCEPTED0.01 s4, 5, 6details
#15ACCEPTED0.02 s4, 5, 6details
#16ACCEPTED0.01 s4, 5, 6details
#17ACCEPTED0.01 s4, 5, 6details
#18ACCEPTED0.08 s5, 6details
#19ACCEPTED0.09 s5, 6details
#20ACCEPTED0.07 s5, 6details
#21ACCEPTED0.07 s5, 6details
#22ACCEPTED0.84 s6details
#23--6details
#24ACCEPTED0.80 s6details
#25ACCEPTED0.96 s6details

Code

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<class T> using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

using ll = long long;
using ull = unsigned long long;
using ld = long double;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

// const ll M = 998244353;
const ll M = 1e9 + 7;
// ll M;


#define all(v) (v).begin(), (v).end()
#define ff first
#define ss second
#define PI 3.141592653589793238462643383279502884L

const ll INFL = 1e18;
const int INF = 1e9;
const ll maxN = 500;
int n;
int st[maxN][maxN][9][9];
int g[maxN][maxN];
ll height[maxN][maxN];

int get(int i1, int  j1, int i2, int j2) {
    // cout << i1 << ' ' << j1  << ' ' << i2 << ' ' << j2 << endl;
    i2++; j2++;
    int k = __lg(i2-i1), l = __lg(j2-j1);
    return 
        st[i1][j1][k][l] |
        st[i2-(1<<k)][j1][k][l] |
        st[i1][j2-(1<<l)][k][l] |
        st[i2-(1<<k)][j2-(1<<l)][k][l];
}

void build() {
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) st[i][j][0][0] = g[i][j];
    }
    for (int k=0; k<=__lg(n); k++) {
        for (int l=0; l<=__lg(n); l++) {
            if (!k && !l) continue;
            for (int i=0; i+(1<<k)<=n; i++) {
                for (int j=0; j+(1<<l)<=n; j++) {
                    if (!k) st[i][j][k][l] = st[i][j][k][l-1]|st[i][j+(1<<(l-1))][k][l-1];
                    else st[i][j][k][l] = st[i][j][k-1][l]|st[i+(1<<(k-1))][j][k-1][l];
                }
            }
        }
    }
}

void solve() {
    cin >> n;
    int target = 0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            char c;
            cin >> c;
            g[i][j] = 1<<(c-'a');
            target |= 1<<(c-'a');
        }
    }
    build();
    ll ans = 0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            for (int k=0; k<=j; k++) {
                while (height[j][k]<=i && get(height[j][k], k, i, j)==target) {
                    height[j][k]++;
                }
                ans += height[j][k];
            }
        }
    }
    cout << ans << '\n';
    
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    cout << setprecision(12);


    int tc = 1;
    // cin >>tc;
    while (tc--) solve();

}

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:

input
500
OIMZGEQSBMBDSDXSWRFNKSGFEBBTJE...

correct output
15575906951

user output
(empty)

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