Submission #373155

#	Time	Username	Problem	Language	Result	Execution time	Memory
373155		Vladth11	Selling RNA Strands (JOI16_selling_rna)	C++14	10 / 100	1600 ms	91888 KiB

selling_rna

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <ll, pii> piii;
typedef tree <pii, null_type, less <pii>, rb_tree_tag, tree_order_statistics_node_update> OST;

const ll NMAX = 2001;
const ll INF = (1LL << 31);
const ll MOD = 1000000007;
const ll BLOCK = 316;
const ll nr_of_bits = 20;
const double eps = 0.0000000001;

vector <pii> events[100001];
int ce[NMAX];

class Trie{
public:
    vector <int> preordine;
    struct Node{
        Node* v[4];
        int first;
        int second;
        set <int> st;
        Node(){
            for(int i = 0; i < 4; i++){
                v[i] = NULL;
            }
        }
    };
    Node* root;
    void insert(Node* &node, string s, int ind, int nr){
        if(node == NULL)
            node = new Node();
        if(ind == s.size()){
            node->st.insert(nr);
            return;
        }
        int c = s[ind] - '0';
        insert(node->v[c], s, ind + 1, nr);
    }
    void DFS(Node* &node){
        if(node == NULL)
            return;
        node->first = preordine.size();
        for(auto x : node->st){
            preordine.push_back(x);
        }
        for(int i = 0; i < 4; i++){
            DFS(node->v[i]);
        }
        node->second = preordine.size() - 1;
    }
    pii interval(Node* &node, string s, int ind){
        if(node == NULL){
            return {-1, -1};
        }
        if(ind == s.size()){
            return {node->first, node->second};
        }
        int c = s[ind] - '0';
        return interval(node->v[c], s, ind + 1);
    }
}pref, suf;

string transforma(string s){
    for(int i = 0; i < s.size(); i++){
        if(s[i] == 'A')
            s[i] = '0';
        if(s[i] == 'G')
            s[i] = '1';
        if(s[i] == 'C')
            s[i] = '2';
        if(s[i] == 'U')
            s[i] = '3';
    }
    return s;
}

int n, m;
int sol[NMAX];
int aib[NMAX];

void update(int x){
    for(int i = x; i <= n; i += i&(-i))
        aib[i]++;
}

int query(int x){
    int v = 0;
    for(int i = x; i > 0; i -= i&(-i))
        v += aib[i];
    return v;
}

void Sweep(){
    for(int i = 1; i <= n; i++){
        update(ce[pref.preordine[i - 1]]);
        for(auto x : events[i]){
            int semn = 1;
            if(x.second < 0)
                semn = -1;
            x.second = abs(x.second);
            sol[x.second] += semn * query(x.first);
        }
    }
}

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        string s;
        cin >> s;
        s = transforma(s);
        pref.insert(pref.root, s, 0, i);
        reverse(s.begin(), s.end());
        suf.insert(suf.root, s, 0, i);
    }
    pref.DFS(pref.root);
    suf.DFS(suf.root);
    for(int i = 0; i < suf.preordine.size(); i++){
        ce[suf.preordine[i]] = i + 1;
    }
    for(int i = 1; i <= m; i++){
        string a, b;
        cin >> a >> b;
        a = transforma(a);
        b = transforma(b);
        reverse(b.begin(), b.end());
        pii timpa = pref.interval(pref.root, a, 0);
        pii timpb = suf.interval(suf.root, b, 0);
        int x1 = timpa.first + 1;
        int x2 = timpa.second + 1;
        int y1 = timpb.first + 1;
        int y2 = timpb.second + 1;
        if(x1 == 0 || y1 == 0){
            sol[i] = 0;
            continue;
        }
        events[x1 - 1].push_back({y1 - 1, i});
        events[x1 - 1].push_back({y2, -i});
        events[x2].push_back({y1 - 1, -i});
        events[x2].push_back({y2, i});
    }
    Sweep();
    for(int i = 1; i <= m; i++){
        cout << sol[i] << "\n";
    }
    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In member function 'void Trie::insert(Trie::Node*&, std::string, int, int)':
selling_rna.cpp:42:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         if(ind == s.size()){
      |            ~~~~^~~~~~~~~~~
selling_rna.cpp: In member function 'pii Trie::interval(Trie::Node*&, std::string, int)':
selling_rna.cpp:65:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         if(ind == s.size()){
      |            ~~~~^~~~~~~~~~~
selling_rna.cpp: In function 'std::string transforma(std::string)':
selling_rna.cpp:74:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int i = 0; i < s.size(); i++){
      |                    ~~^~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:128:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     for(int i = 0; i < suf.preordine.size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40