oj.uz

Submission #1070526

# Submission time Handle Problem Language Result Execution time Memory
1070526 2024-08-22T14:59:53 Z sitablechair Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 90 ms 146004 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];
 
struct Trie{
    struct Node{
        int child[4];
        int exist, cnt;
        int mini=-1;
    } nodes[N*10];
 
    int cur;
    Trie() : cur(0) {
        memset(nodes[0].child, -1, sizeof(nodes[cur].child));
        nodes[0].exist = nodes[0].cnt = 0;
    };
 
    int newn() {
        cur++;
        memset(nodes[cur].child, -1, sizeof(nodes[cur].child));
        nodes[cur].exist = nodes[cur].cnt = 0;
        return cur;
    }
    void add(string s,int ind=0) {
        int pos = 0;
        for (auto f : s) {
            int c = id[f];
            if (nodes[pos].child[c] == -1) {
                nodes[pos].child[c] = newn();
            }
            pos = nodes[pos].child[c];
            nodes[pos].cnt++;
            if (ind) {
                if (nodes[pos].mini==-1) nodes[pos].mini=ind;
                else nodes[pos].mini=min(nodes[pos].mini,ind);
            }
        }
        nodes[pos].exist++;
        
    }
    bool delHandle(int pos, string& s, int i) {
        if (i != (int)s.size()) {
            int c = id[s[i]];
            bool isChildDeleted = delHandle(nodes[pos].child[c], s, i + 1);
            if (isChildDeleted) nodes[pos].child[c] = -1;
        }
        else nodes[pos].exist--;
        if (pos != 0) {
            nodes[pos].cnt--;
            if (nodes[pos].cnt == 0) return true;
        }
        return false;
    }
 
    void del(string &s) {
        if (find(s) == false) return;
        delHandle(0, s, 0);
    }
    bool find(string &s) {
        int pos = 0;
        for (auto f : s) {
            int c = id[f];
            if (nodes[pos].child[c] == -1) return false;
            pos = nodes[pos].child[c];
        }
        return (nodes[pos].exist != 0);
    }
    pair<int,int> get(string &s) {
        int pos=0;
        for(auto f: s) {
            int c=id[f];
            if (nodes[pos].child[c]==-1) return mpa(-1,-1);
            pos=nodes[pos].child[c];
        }
        return mpa(nodes[pos].mini,nodes[pos].mini+nodes[pos].cnt-1);
    }
    int getnum(string &s) {
        int pos=0;
        for(auto f: s) {
            int c=id[f];
            if (nodes[pos].child[c]==-1) return 0;
            pos=nodes[pos].child[c];
        }
        return nodes[pos].cnt;
    }
};
 
ll hilOrd(int x, int y, int pow, int rotate) {
    if (x<0 || y<0) return 1e9;
    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,18,0);
    }
};
Trie trie,trie1;
query qr[N];
string s[N],s1[N];
int n,m,ans[N];
int main() {
    cin.tie(0)->sync_with_stdio(0);
    id['C']=0,id['U']=1,id['G']=2,id['A']=3;
    cin >> n >> m;
    For(i,1,n) cin >> s[i];
    sort(s,s+1+n);
    For(i,1,n) {
        s1[i]=s[i];
        reverse(all(s1[i]));
    }
    For(i,1,n) trie.add(s[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(s1[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) {
            ans[qr[i].ind]=0;
            continue;
        }
        if (r<qr[i].r) For(j,r+1,qr[i].r) trie1.add(s1[j]);
        if (l>qr[i].l) For(j,qr[i].l,l-1) trie1.add(s1[j]);
        if (r>qr[i].l) For(j,qr[i].r+1,r) trie1.del(s1[j]);
        if (l<qr[i].l) For(j,l,qr[i].l-1) trie1.del(s1[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(std::string, int)':
selling_rna.cpp:54:24: warning: array subscript has type 'char' [-Wchar-subscripts]
   54 |             int c = id[f];
      |                        ^
selling_rna.cpp: In member function 'bool Trie::delHandle(int, std::string&, int)':
selling_rna.cpp:70:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   70 |             int c = id[s[i]];
      |                            ^
selling_rna.cpp: In member function 'bool Trie::find(std::string&)':
selling_rna.cpp:89:24: warning: array subscript has type 'char' [-Wchar-subscripts]
   89 |             int c = id[f];
      |                        ^
selling_rna.cpp: In member function 'std::pair<int, int> Trie::get(std::string&)':
selling_rna.cpp:98:22: warning: array subscript has type 'char' [-Wchar-subscripts]
   98 |             int c=id[f];
      |                      ^
selling_rna.cpp: In member function 'int Trie::getnum(std::string&)':
selling_rna.cpp:107:22: warning: array subscript has type 'char' [-Wchar-subscripts]
  107 |             int c=id[f];
      |                      ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 139612 KB Output is correct
2 Correct 39 ms 139672 KB Output is correct
3 Correct 36 ms 139604 KB Output is correct
4 Correct 37 ms 139732 KB Output is correct
5 Correct 36 ms 139612 KB Output is correct
6 Correct 34 ms 139600 KB Output is correct
7 Correct 34 ms 139604 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 90 ms 146004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 140188 KB Output is correct
2 Correct 54 ms 139860 KB Output is correct
3 Correct 61 ms 140100 KB Output is correct
4 Correct 55 ms 139860 KB Output is correct
5 Correct 62 ms 139856 KB Output is correct
6 Correct 63 ms 140036 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 139612 KB Output is correct
2 Correct 39 ms 139672 KB Output is correct
3 Correct 36 ms 139604 KB Output is correct
4 Correct 37 ms 139732 KB Output is correct
5 Correct 36 ms 139612 KB Output is correct
6 Correct 34 ms 139600 KB Output is correct
7 Correct 34 ms 139604 KB Output is correct
8 Incorrect 90 ms 146004 KB Output isn't correct
9 Halted 0 ms 0 KB -