답안 #60270 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
60270	2018-07-23T23:32:23 Z	Benq	Selling RNA Strands (JOI16_selling_rna)	C++11	100 / 100	393 ms	154496 KB

selling_rna

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

int cat(char c) {
    switch(c) {
        case 'A':
            return 0;
        case 'C':
            return 1;
        case 'G':
            return 2;
        default:
            return 3;
    }
}

template<int MX> struct tri {
    int trie[MX][4], nex = 0; // easily changed to character
    int sz[MX], EN[MX];
    
    tri() {
        memset(trie,0,sizeof trie);
    }
    
    void ins(string t) { // insert or delete
        int cur = 0; sz[cur] ++;
        for (char c: t) {
            int C = cat(c);
            if (!trie[cur][C]) {
                trie[cur][C] = ++nex;
                // if U
            }
            cur = trie[cur][C];
            sz[cur] ++;
        }
        EN[cur] ++;
    }
    
    pi getBound(string t) {
        int cur = 0, st = 0;
        for (char c: t) {
            int C = cat(c);
            if (!trie[cur][C]) return {0,-1};
            F0R(i,C) if (trie[cur][i]) {
                // cout << "OOPS " << sz(t) << " " << cur << " " << i <<  " " << trie[cur][i] << "\n";
                st += sz[trie[cur][i]];
            }
            st += EN[cur];
            // cout << "HUH " << cur << " " << EN[cur] << "\n";
            cur = trie[cur][C];
        }
        return {st+1,st+sz[cur]};
    }
};

tri<2000001> t0, t1;

template<class T, int SZ> struct BIT {
    T bit[SZ+1];
    
    BIT() { memset(bit,0,sizeof bit); }
    
    void upd(int k, T val) { // add val to index k
        for( ;k <= SZ; k += (k&-k)) bit[k] += val;
    }
    
    T query(int k) {
        T temp = 0;
        for (;k > 0;k -= (k&-k)) temp += bit[k];
        return temp;
    }
    T query(int l, int r) { return query(r)-query(l-1); } // range query [l,r]
};

BIT<int,MX> B;

int N,M, ans[MX], beg[MX], en[MX];
vector<pair<string,int>> v0, v1;
vector<array<int,3>> v[MX];
vi ad[MX];

void input() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M;
    FOR(i,1,N+1) {
        string s; cin >> s;
        t0.ins(s); v0.pb({s,i}); 
        reverse(all(s));
        t1.ins(s); v1.pb({s,i});
    }
    
    sort(all(v0)), sort(all(v1));
    F0R(i,N) {
        // cout << v0[i].f << " " << t0.getBound(v0[i].f).f << " " << t0.getBound(v0[i].f).s << "\n";
        beg[v0[i].s] = i+1;
        en[v1[i].s] = i+1;
    }
    FOR(i,1,N+1) {
        ad[beg[i]].pb(en[i]);
        // cout << beg[i] << " " << en[i] << "\n";
    }
}

int main() {
    input();
    
    F0R(i,M) {
        string P, Q; cin >> P >> Q; reverse(all(Q));
        pi x = t0.getBound(P), y = t1.getBound(Q);
        // cout << x.f << " " << x.s << " " << y.f << " " << y.s << "\n";
        if (x.f > x.s || y.f > y.s) continue;
        v[x.f-1].pb({y.s,-1,i});
        v[x.f-1].pb({y.f-1,1,i});
        v[x.s].pb({y.s,1,i});
        v[x.s].pb({y.f-1,-1,i});
    }
    FOR(i,1,N+1) {
        for (int y: ad[i]) B.upd(y,1);
        for (auto a: v[i]) ans[a[2]] += a[1]*B.query(a[0]);
    }
    F0R(i,M) cout << ans[i] << "\n";
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	57 ms	68088 KB	Output is correct
2	Correct	55 ms	68200 KB	Output is correct
3	Correct	55 ms	68200 KB	Output is correct
4	Correct	57 ms	68260 KB	Output is correct
5	Correct	61 ms	68344 KB	Output is correct
6	Correct	68 ms	68348 KB	Output is correct
7	Correct	71 ms	68348 KB	Output is correct

Subtask #2
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	115 ms	85084 KB	Output is correct
2	Correct	128 ms	91316 KB	Output is correct
3	Correct	123 ms	94412 KB	Output is correct
4	Correct	135 ms	99092 KB	Output is correct
5	Correct	152 ms	105372 KB	Output is correct
6	Correct	153 ms	108096 KB	Output is correct
7	Correct	106 ms	108096 KB	Output is correct
8	Correct	165 ms	112620 KB	Output is correct
9	Correct	153 ms	116720 KB	Output is correct
10	Correct	118 ms	119872 KB	Output is correct

Subtask #3
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	140 ms	119872 KB	Output is correct
2	Correct	105 ms	119872 KB	Output is correct
3	Correct	162 ms	119872 KB	Output is correct
4	Correct	112 ms	119872 KB	Output is correct
5	Correct	106 ms	119872 KB	Output is correct
6	Correct	160 ms	119872 KB	Output is correct

Subtask #4
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	57 ms	68088 KB	Output is correct
2	Correct	55 ms	68200 KB	Output is correct
3	Correct	55 ms	68200 KB	Output is correct
4	Correct	57 ms	68260 KB	Output is correct
5	Correct	61 ms	68344 KB	Output is correct
6	Correct	68 ms	68348 KB	Output is correct
7	Correct	71 ms	68348 KB	Output is correct
8	Correct	115 ms	85084 KB	Output is correct
9	Correct	128 ms	91316 KB	Output is correct
10	Correct	123 ms	94412 KB	Output is correct
11	Correct	135 ms	99092 KB	Output is correct
12	Correct	152 ms	105372 KB	Output is correct
13	Correct	153 ms	108096 KB	Output is correct
14	Correct	106 ms	108096 KB	Output is correct
15	Correct	165 ms	112620 KB	Output is correct
16	Correct	153 ms	116720 KB	Output is correct
17	Correct	118 ms	119872 KB	Output is correct
18	Correct	140 ms	119872 KB	Output is correct
19	Correct	105 ms	119872 KB	Output is correct
20	Correct	162 ms	119872 KB	Output is correct
21	Correct	112 ms	119872 KB	Output is correct
22	Correct	106 ms	119872 KB	Output is correct
23	Correct	160 ms	119872 KB	Output is correct
24	Correct	172 ms	131156 KB	Output is correct
25	Correct	178 ms	137824 KB	Output is correct
26	Correct	155 ms	138216 KB	Output is correct
27	Correct	180 ms	142772 KB	Output is correct
28	Correct	393 ms	154496 KB	Output is correct
29	Correct	278 ms	154496 KB	Output is correct

답안 #60270

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 25.0 / 25.0

Subtask #3 25.0 / 25.0

Subtask #4 40.0 / 40.0

Subtask #1
10.0 / 10.0

Subtask #2
25.0 / 25.0

Subtask #3
25.0 / 25.0

Subtask #4
40.0 / 40.0