oj.uz

Submission #1070542

# Submission time Handle Problem Language Result Execution time Memory
1070542 2024-08-22T15:09:27 Z sitablechair Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 242 ms 170532 KB 
#include <bits/stdc++.h>

#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define REP(i,l,r) For(i,l,r-1)
#define PER(i,r,l) ForD(i,r-1,l)
#define ff first
#define ss second
#define pb emplace_back
#define all(x) x.begin(),x.end()
#define All(x,n) x+1,x+1+n
#define Alll(x,n) x,x+n
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define mpa make_pair

#ifdef NCGM
#include"debug.h"
#else 
#define debug(...) "fr";
#endif

using namespace std;

const int N=2e5+9;

int id[500],sus=0;

struct Trie{
    struct Node{
        Node* child[4];
        int exist, cnt,mini=-1;

        Node() {
            for (int i = 0; i < 4; i++) child[i] = NULL;
            exist = cnt = 0;
        }
    };

    int cur;
    Node* root;
    Trie() : cur(0) {
        root = new Node();
    };

    void add_string(string s,int ind=0) {
        Node* p = root;
        for (auto f : s) {
            int c = id[f];
            if (p->child[c] == NULL) p->child[c] = new Node();
            p = p->child[c];
            if (ind) {
                if (p->mini==-1) p->mini=ind;
                else p->mini=min(p->mini,ind);
            }
            p->cnt++;
        }
        p->exist++;
    }
    bool delete_string_recursive(Node* p, string& s, int i) {
        if (i != (int)s.size()) {
            int c = id[s[i]];
            bool isChildDeleted = delete_string_recursive(p->child[c], s, i + 1);
            if (isChildDeleted) p->child[c] = NULL;
        }
        else p->exist--;

        if (p != root) {
            p->cnt--;
            if (p->cnt == 0) {
                delete(p);
                return true;
            }
        }
        return false;
    }

    void delete_string(string s) {
        if (find_string(s) == false) return;

        delete_string_recursive(root, s, 0);
    }

    bool find_string(string s) {
        Node* p = root;
        for (auto f : s) {
            int c = id[f];
            if (p->child[c] == NULL) return false;
            p = p->child[c];
        }
        return (p->exist != 0);
    }
    pair<int,int> get(string s) {
        Node* p = root;
        for (auto f : s) {
            int c = id[f];
            if (p->child[c] == NULL) return mpa(-1,-1);
            p = p->child[c];
        }
        return mpa(p->mini,p->mini+p->cnt-1);
    }
    int getnum(string s) {
        Node* p = root;
        for (auto f : s) {
            int c = id[f];
            if (p->child[c] == NULL) return 0;
            p = p->child[c];
        }
        return p->cnt;
    }
};

ll hilOrd(int x, int y, int pow, int rotate) {
    if (x<0 || y<0) return 2LL*1e18;
    if (pow == 0) return 0;
    int hpow = 1 << (pow-1);
    int seg = (x < hpow) ? ((y < hpow) ? 0 : 3) : ((y < hpow) ? 1 : 2);
    seg = (seg + rotate) & 3;
    const int rotateDelta[4] = {3, 0, 0, 1};
    int nx = x & (x ^ hpow), ny = y & (y ^ hpow);
    int nrot = (rotate + rotateDelta[seg]) & 3;
    ll subSquareSize = int64_t(1) << (2*pow - 2);
    ll ans = seg * subSquareSize;
    ll add = hilOrd(nx, ny, pow-1, nrot);
    ans += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);
    return ans;
}

struct query {
    int l,r,ind;
    ll order=0;
    string p,q;
    void calOrd() {
        order=hilOrd(l,r,20,0);
    }
};
bool isPrefix(string &s,string s1) {
    if (sz(s)<sz(s1)) return 0;
    For(i,0,sz(s1)-1) if (s[i]!=s1[i]) return 0;
    return 1;
}
Trie trie,trie1;
query qr[N];
string a[N],a1[N];
int n,m,ans[N],tmp=0;
int main() {
    cin.tie(0)->sync_with_stdio(0);
    id['C']=0,id['U']=1,id['G']=2,id['A']=3;
    /*freopen("D.INP","r",stdin);
    freopen("D.OUT","w",stdout);*/
    cin >> n >> m;
    For(i,1,n) cin >> a[i];
    sort(a,a+1+n);
    For(i,1,n) {
        a1[i]=a[i];
        reverse(all(a1[i]));
    }
    For(i,1,n) trie.add_string(a[i],i);  
    For(i,1,m) {
        cin >> qr[i].p >> qr[i].q;
        reverse(all(qr[i].q));
        qr[i].ind=i;
        pair<int,int> sus=trie.get(qr[i].p);
        qr[i].l=sus.ff;
        qr[i].r=sus.ss;
        qr[i].calOrd();
    } 
    sort(qr+1,qr+1+m,[](const query &A, const query &B) {
        return A.order<B.order;
    });
    fill(ans,ans+1+n,0);
    int l=qr[1].l,r=qr[1].r;   
    For(i,qr[1].l,qr[1].r) {
        if (i<0) break;
        trie1.add_string(a1[i]);
    }
    if (qr[1].l>0 && qr[1].r>0) ans[qr[1].ind]=trie1.getnum(qr[1].q);
    For(i,2,m) {
        if (qr[i].l<0 || qr[i].r<0) break;
        if (l>qr[i].l) For(j,qr[i].l,l-1) trie1.add_string(a1[j]);
        if (r<qr[i].r) For(j,r+1,qr[i].r) trie1.add_string(a1[j]);
        if (l<qr[i].l) For(j,l,qr[i].l-1) trie1.delete_string(a1[j]);
        if (r>qr[i].l) For(j,qr[i].r+1,r) trie1.delete_string(a1[j]);
        l=qr[i].l,r=qr[i].r;
        ans[qr[i].ind]=trie1.getnum(qr[i].q);
    }
    For(i,1,m) cout << ans[i] << endl;
    return 0;
}

Compilation message

selling_rna.cpp: In member function 'void Trie::add_string(std::string, int)':
selling_rna.cpp:52:24: warning: array subscript has type 'char' [-Wchar-subscripts]
   52 |             int c = id[f];
      |                        ^
selling_rna.cpp: In member function 'bool Trie::delete_string_recursive(Trie::Node*, std::string&, int)':
selling_rna.cpp:65:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   65 |             int c = id[s[i]];
      |                            ^
selling_rna.cpp: In member function 'bool Trie::find_string(std::string)':
selling_rna.cpp:90:24: warning: array subscript has type 'char' [-Wchar-subscripts]
   90 |             int c = id[f];
      |                        ^
selling_rna.cpp: In member function 'std::pair<int, int> Trie::get(std::string)':
selling_rna.cpp:99:24: warning: array subscript has type 'char' [-Wchar-subscripts]
   99 |             int c = id[f];
      |                        ^
selling_rna.cpp: In member function 'int Trie::getnum(std::string)':
selling_rna.cpp:108:24: warning: array subscript has type 'char' [-Wchar-subscripts]
  108 |             int c = id[f];
      |                        ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 30808 KB Output is correct
2 Correct 5 ms 30812 KB Output is correct
3 Correct 5 ms 30812 KB Output is correct
4 Correct 5 ms 30812 KB Output is correct
5 Correct 5 ms 30792 KB Output is correct
6 Correct 4 ms 30812 KB Output is correct
7 Correct 5 ms 30812 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 162640 KB Output is correct
2 Correct 186 ms 155984 KB Output is correct
3 Correct 133 ms 160852 KB Output is correct
4 Correct 142 ms 155112 KB Output is correct
5 Correct 221 ms 169556 KB Output is correct
6 Correct 242 ms 170532 KB Output is correct
7 Correct 69 ms 41300 KB Output is correct
8 Correct 119 ms 89168 KB Output is correct
9 Correct 165 ms 82512 KB Output is correct
10 Correct 70 ms 111260 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 31552 KB Output is correct
2 Correct 24 ms 31592 KB Output is correct
3 Correct 29 ms 31504 KB Output is correct
4 Correct 26 ms 31324 KB Output is correct
5 Correct 28 ms 31684 KB Output is correct
6 Correct 32 ms 31580 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 30808 KB Output is correct
2 Correct 5 ms 30812 KB Output is correct
3 Correct 5 ms 30812 KB Output is correct
4 Correct 5 ms 30812 KB Output is correct
5 Correct 5 ms 30792 KB Output is correct
6 Correct 4 ms 30812 KB Output is correct
7 Correct 5 ms 30812 KB Output is correct
8 Correct 223 ms 162640 KB Output is correct
9 Correct 186 ms 155984 KB Output is correct
10 Correct 133 ms 160852 KB Output is correct
11 Correct 142 ms 155112 KB Output is correct
12 Correct 221 ms 169556 KB Output is correct
13 Correct 242 ms 170532 KB Output is correct
14 Correct 69 ms 41300 KB Output is correct
15 Correct 119 ms 89168 KB Output is correct
16 Correct 165 ms 82512 KB Output is correct
17 Correct 70 ms 111260 KB Output is correct
18 Correct 33 ms 31552 KB Output is correct
19 Correct 24 ms 31592 KB Output is correct
20 Correct 29 ms 31504 KB Output is correct
21 Correct 26 ms 31324 KB Output is correct
22 Correct 28 ms 31684 KB Output is correct
23 Correct 32 ms 31580 KB Output is correct
24 Correct 130 ms 140372 KB Output is correct
25 Correct 118 ms 140676 KB Output is correct
26 Correct 156 ms 139008 KB Output is correct
27 Correct 128 ms 138888 KB Output is correct
28 Correct 122 ms 54876 KB Output is correct
29 Correct 85 ms 33108 KB Output is correct