CSES - Datatähti 2025 alku - Results
Submission details
Task:Niitty
Sender:anotn
Submission time:2024-11-03 18:21:24 +0200
Language:C++ (C++17)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
#50
#60
Test results
testverdicttimegroup
#10.00 s1, 2, 3, 4, 5, 6details
#2ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#30.00 s1, 2, 3, 4, 5, 6details
#4ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#50.00 s1, 2, 3, 4, 5, 6details
#60.00 s2, 3, 4, 5, 6details
#70.00 s2, 3, 4, 5, 6details
#80.00 s2, 3, 4, 5, 6details
#9ACCEPTED0.00 s2, 3, 4, 5, 6details
#100.01 s3, 4, 5, 6details
#110.02 s3, 4, 5, 6details
#120.00 s3, 4, 5, 6details
#13ACCEPTED0.03 s3, 4, 5, 6details
#140.01 s4, 5, 6details
#150.12 s4, 5, 6details
#160.01 s4, 5, 6details
#17ACCEPTED0.36 s4, 5, 6details
#180.03 s5, 6details
#190.83 s5, 6details
#200.01 s5, 6details
#21--5, 6details
#220.14 s6details
#23--6details
#240.05 s6details
#25--6details

Code

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;


int tree_size = 1;


int tree_range( vector<int>& tree, int a, int b ) {
    a += tree_size;
    b += tree_size;

    int s = 0;

    while (a <= b) {
        if (a%2 == 1) s |= tree[a++];
        if (b%2 == 0) s |= tree[b--];
        a /= 2; b /= 2;
    }

    return s;
}


bool area_check(vector<vector<int>>& field, int flowers_amount, int& x1, int& y1, int& x2, int& y2) {
    
    int current = 0;
    for ( int y = y1; y <= y2; y++ ) {
        current |= tree_range(field[y], x1, x2);
        if ( current == ((1<<flowers_amount)-1) )
            return true;
    }

    return false;
}


void tree_insert ( vector<int>& tree, int x, int i ) {
    i += tree_size;
    tree[i] = x;

    for ( i /= 2; i >= 1; i /= 2 )
        tree[i] = tree[i*2] | tree[i*2+1];
}



int main () {
    int n;
    cin >> n;
    
    while ( tree_size < n )
        tree_size <<= 1;


    unordered_map<char, int> flowers;
    vector<vector<int>> field(n, vector<int>(2*tree_size, 0));
    for ( int i = 0; i < n; i++ ) {
        for ( int j = 0; j < n; j++ ) {
            char c;
            cin >> c;
            
            if ( flowers.find(c) == flowers.end() )
                flowers[c] = flowers.size();

            tree_insert(field[i], 1<<flowers[c], j);
        }
    }


    int count = 0;


    for ( int y1 = 0; y1 < n; y1++ ) {
        for ( int x1 = 0; x1 < n; x1++ ) {
            int x2 = n-1;
            int y2 = y1;

            while ( y2 < n && !area_check(field, flowers.size(), x1, y1, x2, y2) )
                y2++;

            x2 = x1;
            while ( x2 < n && y2 < n && !area_check(field, flowers.size(), x1, y1, x2, y2) )
                x2++;

            count += (n - x2) * (n - y2);

            int y3 = y1;

            while ( y3 < n && !area_check(field, flowers.size(), x1, y1, x1, y3) )
                y3++;
            count += n - y3;

            if ( x2 == n )
                break;
        }
    }

    cout << count;
}

Test details

Test 1

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

Verdict:

input
10
TNCTNPNTPC
NPPNTNTPTP
NTNTTCNTCT
NPCPNPPNTT
...

correct output
2035

user output
1453

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:

input
10
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
...

correct output
3025

user output
3575

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:

input
1
X

correct output
1

user output
2

Test 6

Group: 2, 3, 4, 5, 6

Verdict:

input
20
BBCBUBOUOBBCUUBBCOUO
BOUCOOCUBCOOOCOBOCUO
UCCUUUOBCOCBCBUBUCOO
BUOBUCUCUOOBCOOUBUOO
...

correct output
38724

user output
27106

Test 7

Group: 2, 3, 4, 5, 6

Verdict:

input
20
CBGLSHGZHYZDWBNDBJUG
SMUXOJQYPXZDTMJUIWOJ
XIDSTNBGHKRKOVUVMINB
MTQGCFRUHQKALXRNCQGS
...

correct output
8334

user output
5864

Test 8

Group: 2, 3, 4, 5, 6

Verdict:

input
20
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
...

correct output
44100

user output
48300

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:

input
50
GRGREEEGREGXRXXEGXXREXGRRRGRRR...

correct output
1584665

user output
1279307

Test 11

Group: 3, 4, 5, 6

Verdict:

input
50
AITIISJUHCCRZNKSDCNQKYSQRINFWJ...

correct output
1077746

user output
352981

Test 12

Group: 3, 4, 5, 6

Verdict:

input
50
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

correct output
1625625

user output
1689375

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:

input
100
NNCMDCDDCCNNNDNCMMNCDCDCCDCDNM...

correct output
25325366

user output
22481381

Test 15

Group: 4, 5, 6

Verdict:

input
100
LIMQQIHASECROEVILNVULGWZJPPKOG...

correct output
22342463

user output
7291841

Test 16

Group: 4, 5, 6

Verdict:

input
100
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTT...

correct output
25502500

user output
26007500

Test 17

Group: 4, 5, 6

Verdict: ACCEPTED

input
100
QXQQQQQQQQQQQQQQQQQQQQQQQQQQQQ...

correct output
25650

user output
25650

Test 18

Group: 5, 6

Verdict:

input
200
NAANANMMKNKKAKMKMAKNKMNKMMNNAA...

correct output
403292767

user output
379152167

Test 19

Group: 5, 6

Verdict:

input
200
OMYWATTLURKQPTKEFMGGYAOONXWVSC...

correct output
388111321

user output
158980827

Test 20

Group: 5, 6

Verdict:

input
200
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCC...

correct output
404010000

user output
408030000

Test 21

Group: 5, 6

Verdict:

input
200
LLLLLLLLLLLLLLLLLHLLLLLLLLLLLL...

correct output
14159445

user output
(empty)

Test 22

Group: 6

Verdict:

input
500
VVHWVUHVHUWWWVUUUWVUUHUUWHWUVW...

correct output
15683003812

user output
-1884062340

Test 23

Group: 6

Verdict:

input
500
OIMZGEQSBMBDSDXSWRFNKSGFEBBTJE...

correct output
15575906951

user output
(empty)

Test 24

Group: 6

Verdict:

input
500
IIIIIIIIIIIIIIIIIIIIIIIIIIIIII...

correct output
15687562500

user output
-1429681684

Test 25

Group: 6

Verdict:

input
500
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWW...

correct output
3058970930

user output
(empty)