21 Days Training // Day 7

3. water

HOW DARE YOU! IS THIS A WATER PROBLEM?

My idea : online, BF(-ish) search

#include <bits/stdc++.h>
using namespace std;

int main() {
    freopen("water.in", "r", stdin);
    freopen("water.out", "w", stdout);
    int N, D;cin >> N >> D;
    string S[N];
    for (int i=0;i<N;i++) cin >> S[i];
    int Q;cin >> Q;
    for (int i=0;i<Q;i++) {
        int opt;cin >> opt;
        string X;cin >> X;
        if (opt==1) {
            long long cnt=0;
            for (int j=0;j<N;j++) {
                for (int k=0;k<D;k++) {
                    if (S[j][k]>X[k]) goto scan1_end ;
                }
                cnt++;
                scan1_end: ;
            } 
            cout << cnt*(cnt-1)/2;
        }
        else if (opt==2) {
            long long cnt=0;
            for (int j=0;j<N;j++) {
                for (int k=0;k<D;k++) {
                    if (S[j][k]<X[k]) goto scan2_end ;
                }
                cnt++;
                scan2_end: ;
            } 
            cout << cnt*(cnt-1)/2;
        }
        else {
            long long ps=0;
            for (int j=0;j<N-1;j++) {
                for (int k=j+1;k<N;k++) {
                    string M1, M2;
                    for (int d=0;d<D;d++) M1 += max(S[j][d], S[k][d]), M2 += min(S[j][d], S[k][d]);
                    for (int d=0;d<D;d++) {
                        if (opt==3&&M1[d]<X[d]) goto enum_end ;
                        if (opt==4&&M2[d]>X[d]) goto enum_end ;
                    }
                    ps++;
                    enum_end: ;
                } 
            }
            cout << ps;
        }
        cout << endl;

    } 
    return 0;
}

Optimize :
Notice that for query 1, 2, if string A or B does not satisfy the condition, the pair (A, B) does not satisfy it.
So, for query 1, 2, we can scan all strings given, and find those are strictly greater or equals to C, the use formula C_n^2 = \frac{n(n-1)}{2} to count.
(Line 15-34. )

Complexity : from O(nmq) to O(n^2mq) .

Constraints :

With the bad luck, I cannot even pass the case 1.