oj.uz

답안 #1071025

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1071025 2024-08-23T01:34:38 Z sitablechair Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 255 ms 158864 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,BLOCK=330;
 
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;
    string p,q;
};
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;
    } 
    sort(qr+1,qr+1+m,[](const query &A, const query &B) {
        if (A.l/BLOCK!=B.l/BLOCK) return A.l/BLOCK<B.l/BLOCK;
        return A.r<B.r;
    });
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 29272 KB Output is correct
2 Correct 4 ms 29272 KB Output is correct
3 Correct 4 ms 29276 KB Output is correct
4 Correct 4 ms 29276 KB Output is correct
5 Correct 4 ms 29276 KB Output is correct
6 Correct 4 ms 29276 KB Output is correct
7 Correct 4 ms 29128 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 221 ms 158864 KB Output is correct
2 Correct 217 ms 152312 KB Output is correct
3 Correct 250 ms 157012 KB Output is correct
4 Correct 162 ms 150864 KB Output is correct
5 Correct 190 ms 129072 KB Output is correct
6 Correct 189 ms 130896 KB Output is correct
7 Correct 227 ms 36708 KB Output is correct
8 Correct 109 ms 82516 KB Output is correct
9 Correct 102 ms 74736 KB Output is correct
10 Correct 73 ms 107600 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 29524 KB Output is correct
2 Correct 19 ms 29788 KB Output is correct
3 Correct 24 ms 29568 KB Output is correct
4 Correct 19 ms 29524 KB Output is correct
5 Correct 24 ms 29784 KB Output is correct
6 Correct 27 ms 29632 KB Output is correct

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 29272 KB Output is correct
2 Correct 4 ms 29272 KB Output is correct
3 Correct 4 ms 29276 KB Output is correct
4 Correct 4 ms 29276 KB Output is correct
5 Correct 4 ms 29276 KB Output is correct
6 Correct 4 ms 29276 KB Output is correct
7 Correct 4 ms 29128 KB Output is correct
8 Correct 221 ms 158864 KB Output is correct
9 Correct 217 ms 152312 KB Output is correct
10 Correct 250 ms 157012 KB Output is correct
11 Correct 162 ms 150864 KB Output is correct
12 Correct 190 ms 129072 KB Output is correct
13 Correct 189 ms 130896 KB Output is correct
14 Correct 227 ms 36708 KB Output is correct
15 Correct 109 ms 82516 KB Output is correct
16 Correct 102 ms 74736 KB Output is correct
17 Correct 73 ms 107600 KB Output is correct
18 Correct 26 ms 29524 KB Output is correct
19 Correct 19 ms 29788 KB Output is correct
20 Correct 24 ms 29568 KB Output is correct
21 Correct 19 ms 29524 KB Output is correct
22 Correct 24 ms 29784 KB Output is correct
23 Correct 27 ms 29632 KB Output is correct
24 Correct 242 ms 136528 KB Output is correct
25 Correct 255 ms 136844 KB Output is correct
26 Correct 208 ms 134992 KB Output is correct
27 Correct 121 ms 134856 KB Output is correct
28 Correct 107 ms 50680 KB Output is correct
29 Correct 66 ms 29776 KB Output is correct