oj.uz

Submission #1048143

# Submission time Handle Problem Language Result Execution time Memory
1048143 2024-08-08T01:48:44 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
60 / 100
 93 ms 65404 KB 
#include<bits/stdc++.h>
using namespace std;
#define FOR(i, a, b)  for(int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, b, a) for(int i = (b), _a = (a); i >= _a; --i)
#define REP(i, a, b)  for(int i = (a), _b = (b); i < _b;  ++i)
#define REPD(i, b, a) for(int i = (b), _a = (a); i > _a;  --i)
#define MASK(i) (1LL << (i))
#define BIT(mask, i) (((mask) >> (i)) & 1)
#define __builtin_popcount __builtin_popcountll
#define all(val) val.begin(), val.end()
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sz(v) (int)v.size()
#define fi first
#define se second

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll Rand(ll l, ll r) {return l + rng() % (r - l + 1);}

template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        if (x > y) {
            x = y;
            return true;
        } else return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        } else return false;
    }
template<class T>
    T Abs(const T &x) {
        return (x < 0 ? -x : x);
    }

const int mod = 1e9 + 7;
const int inf = 1e9;
const int N = 1e5 + 5;

struct node {
    int val, l, r;
    node() {
        val = l = r = 0;
    }
};

int n, q, nNodes, ver[N];
string s[N], rev[N];
vector<pair<string, int>> v;
node st[(1 << 20) + 5];

void upd(int id) {
    st[id].val = st[st[id].l].val + st[st[id].r].val;
}

int update(int pos, int val, int old, int l = 1, int r = n) {
    int cur = ++nNodes;
    if(l == r) {
        st[cur].val = st[old].val + val;
        return cur;
    }
    int m = l + r >> 1;
    if(pos <= m) {
        st[cur].l = update(pos, val, st[old].l, l, m);
        st[cur].r = st[old].r;
    }
    else {
        st[cur].l = st[old].l;
        st[cur].r = update(pos, val, st[old].r, m + 1, r);
    }
    upd(cur);
    return cur;
}

int get(int ver1, int ver2, int u, int v, int l = 1, int r = n) {
    if(u > r || v < l) return 0;
    if(u <= l && r <= v) {
        return st[ver2].val - st[ver1].val;
    }
    int m = l + r >> 1;
    return get(st[ver1].l, st[ver2].l, u, v, l, m) + get(st[ver1].r, st[ver2].r, u, v, m + 1, r);
}

pii Find(string x, string *S) {
    int l = lower_bound(S + 1, S + n + 1, x) - S;
    x.back()++;
    int r = lower_bound(S + 1, S + n + 1, x) - S - 1;
    return {l, r};
}

void process() {
    cin >> n >> q;
    FOR(i, 1, n) cin >> s[i];
    sort(s + 1, s + n + 1);
    FOR(i, 1, n) {
        rev[i] = s[i];
        reverse(all(rev[i]));
        v.emplace_back(rev[i], i);
    }
    sort(rev + 1, rev + n + 1);
    sort(all(v));
    FOR(i, 1, n) {
        ver[i] = update(v[i - 1].se, 1, ver[i - 1]);
    }
    while(q--) {
        string pref, suf; cin >> pref >> suf;
        reverse(all(suf));
        auto [l1, r1] = Find(pref, s);
        auto [l2, r2] = Find(suf, rev);
        cout << get(ver[l2 - 1], ver[r2], l1, r1) << '\n';
    }
}

signed main() {
    if(fopen("test.inp","r")) {
        freopen("test.inp","r",stdin);
        freopen("test.out","w",stdout);
    }
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    // clock_t start = clock();

    int ntests = 1;
    // cin >> ntests;
    while(ntests--) process();

    // cerr << "Time elapsed: " << clock() - start << " ms!\n";
    return 0;
}

Compilation message

selling_rna.cpp: In function 'int update(int, int, int, int, int)':
selling_rna.cpp:67:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |     int m = l + r >> 1;
      |             ~~^~~
selling_rna.cpp: In function 'int get(int, int, int, int, int, int)':
selling_rna.cpp:85:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |     int m = l + r >> 1;
      |             ~~^~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:121:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:122:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         freopen("test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19036 KB Output is correct
2 Correct 4 ms 19100 KB Output is correct
3 Correct 3 ms 19032 KB Output is correct
4 Correct 2 ms 19036 KB Output is correct
5 Correct 2 ms 19036 KB Output is correct
6 Correct 3 ms 19036 KB Output is correct
7 Correct 2 ms 19036 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 29020 KB Output is correct
2 Correct 18 ms 29320 KB Output is correct
3 Correct 19 ms 29088 KB Output is correct
4 Correct 21 ms 29460 KB Output is correct
5 Correct 16 ms 25520 KB Output is correct
6 Correct 15 ms 25528 KB Output is correct
7 Correct 16 ms 29020 KB Output is correct
8 Correct 23 ms 31184 KB Output is correct
9 Correct 23 ms 31152 KB Output is correct
10 Correct 20 ms 28856 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 21964 KB Output is correct
2 Correct 30 ms 20756 KB Output is correct
3 Correct 37 ms 21968 KB Output is correct
4 Correct 29 ms 22992 KB Output is correct
5 Correct 29 ms 20840 KB Output is correct
6 Correct 37 ms 21968 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19036 KB Output is correct
2 Correct 4 ms 19100 KB Output is correct
3 Correct 3 ms 19032 KB Output is correct
4 Correct 2 ms 19036 KB Output is correct
5 Correct 2 ms 19036 KB Output is correct
6 Correct 3 ms 19036 KB Output is correct
7 Correct 2 ms 19036 KB Output is correct
8 Correct 13 ms 29020 KB Output is correct
9 Correct 18 ms 29320 KB Output is correct
10 Correct 19 ms 29088 KB Output is correct
11 Correct 21 ms 29460 KB Output is correct
12 Correct 16 ms 25520 KB Output is correct
13 Correct 15 ms 25528 KB Output is correct
14 Correct 16 ms 29020 KB Output is correct
15 Correct 23 ms 31184 KB Output is correct
16 Correct 23 ms 31152 KB Output is correct
17 Correct 20 ms 28856 KB Output is correct
18 Correct 42 ms 21964 KB Output is correct
19 Correct 30 ms 20756 KB Output is correct
20 Correct 37 ms 21968 KB Output is correct
21 Correct 29 ms 22992 KB Output is correct
22 Correct 29 ms 20840 KB Output is correct
23 Correct 37 ms 21968 KB Output is correct
24 Correct 32 ms 29784 KB Output is correct
25 Correct 53 ms 29864 KB Output is correct
26 Correct 27 ms 29916 KB Output is correct
27 Correct 34 ms 29812 KB Output is correct
28 Runtime error 93 ms 65404 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -