oj.uz

Submission #153616

# Submission time Handle Problem Language Result Execution time Memory
153616 2019-09-15T03:21:50 Z 12tqian Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 1283 ms 142488 KB 
#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#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;
template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const double PI = 4 * atan(1);

#define sz(x) (int)(x).size()
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define vi vector<int>
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define vpi vector<pair<int, int>>
#define vpd vector<pair<double, double>>
#define pd pair<double, double>

#define f0r(i,a) for(int i=0;i<a;i++)
#define f1r(i,a,b) for(int i=a;i<b;i++)

template<typename A, typename B> ostream& operator <<(ostream &cout, pair< A, B> const &p) {return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename A> ostream& operator <<(ostream &cout, vector<A> const &v){
    cout <<"["; for(int i = 0; i<v.size(); i++) {if(i) cout <<", "; cout << v[i];} return cout << "]";
}
void fast_io(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}
void io(string taskname){
    string fin = taskname + ".in";
    string fout = taskname + ".out";
    const char* FIN = fin.c_str();
    const char* FOUT = fout.c_str();
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
    fast_io();
}

const int SZ = (1<<19);
const int MAX = 1e5 + 5;
const int ALPH = 4;
const int VALS = 2e6 + 5;
const int INF = 1e9;
int n, m;

pii pts[MAX];
pair<pii, pii> queries[MAX];

template<class T> struct node {
    T val;
    node<T>* c[2];

    node() {
        val = 0;
        c[0] = c[1] = NULL;
    }

    void upd(int ind, T v, int L = 0, int R = SZ-1) { // add v
        if (L == ind && R == ind) { val += v; return; }

        int M = (L+R)/2;
        if (ind <= M) {
            if (!c[0]) c[0] = new node();
            c[0]->upd(ind,v,L,M);
        } else {
            if (!c[1]) c[1] = new node();
            c[1]->upd(ind,v,M+1,R);
        }

        val = 0;
        if (c[0]) val += c[0]->val;
        if (c[1]) val += c[1]->val;
    }

    T query(int low, int high, int L = 0, int R = SZ-1) { // query sum of segment
        if (low <= L && R <= high) return val;
        if (high < L || R < low) return 0;

        int M = (L+R)/2;
        T t = 0;
        if (c[0]) t += c[0]->query(low,high,L,M);
        if (c[1]) t += c[1]->query(low,high,M+1,R);
        return t;
    }

    void UPD(int ind, node* c0, node* c1, int L = 0, int R = SZ-1) { // for 2D segtree
        if (L != R) {
            int M = (L+R)/2;
            if (ind <= M) {
                if (!c[0]) c[0] = new node();
                c[0]->UPD(ind,c0 ? c0->c[0] : NULL,c1 ? c1->c[0] : NULL,L,M);
            } else {
                if (!c[1]) c[1] = new node();
                c[1]->UPD(ind,c0 ? c0->c[1] : NULL,c1 ? c1->c[1] : NULL,M+1,R);
            }
        }
        val = 0;
        if (c0) val += c0->val;
        if (c1) val += c1->val;
    }
};
template<class T> struct Node {
    node<T> seg;
    Node* c[2];

    void upd(int x, int y, T v, int L = 0, int R = SZ-1) { // add v
        if (L == x && R == x) {
            seg.upd(y,v);
            return;
        }

        int M = (L+R)/2;
        if (x <= M) {
            if (!c[0]) c[0] = new Node();
            c[0]->upd(x,y,v,L,M);
        } else {
            if (!c[1]) c[1] = new Node();
            c[1]->upd(x,y,v,M+1,R);
        }

        seg.UPD(y,c[0] ? &c[0]->seg : NULL,c[1] ? &c[1]->seg : NULL);
    }

    T query(int x1, int x2, int y1, int y2, int L = 0, int R = SZ-1) { // query sum of rectangle
        if (x1 <= L && R <= x2) return seg.query(y1,y2);
        if (x2 < L || R < x1) return 0;

        int M = (L+R)/2;
        T t = 0;
        if (c[0]) t += c[0]->query(x1,x2,y1,y2,L,M);
        if (c[1]) t += c[1]->query(x1,x2,y1,y2,M+1,R);
        return t;
    }
};
template<class T> struct SegBit {
    node<T> seg[SZ+1];

    SegBit() {
        f0r(i,SZ+1) seg[i] = node<T>();
    }

    void upd(int x, int y, int v) { // add v
        for (x++;x <= SZ; x += (x&-x)) seg[x].upd(y,v);
    }

    T query(int x, int y1, int y2) {
        T ret = 0;
        for (;x > 0; x -= (x&-x)) ret += seg[x].query(y1,y2);
        return ret;
    }

    T query(int x1, int x2, int y1, int y2) { // query sum of rectangle
        return query(x2+1,y1,y2)-query(x1,y1,y2);
    }
};
template<int LEN> struct Trie{
    int t[LEN][ALPH];
    int loc[LEN];
    int root = 0;
    int vals = 1;
    int ok = 0;
    unordered_map<int, int> um;
    pii bounds[LEN];
    vi v;
    void build(){
        f0r(i, LEN) f0r(j, ALPH) t[i][j] = -1;
    }
    int get(char c){
        if(c == 'A') return 0;
        else if(c == 'U') return 1;
        else if (c == 'G') return 2;
        return 3;
    }
    void ins(string s, int idx){
        int sz = sz(s);
        int cur = root;
        f0r(i, sz){
            int g = get(s[i]);
            if(t[cur][g] == -1){
                t[cur][g] = vals;
                cur = vals;
                vals++;
            }
            else{
                cur = t[cur][g];
            }
        }
        um[idx] = cur;
    }
    void euler(){
        dfs(root);
        f0r(i, n){
            if(ok == 0){
                pts[i].f = loc[um[i]];
            }
            else{
                pts[i].s = loc[um[i]];
            }
        }
        f0r(i, m){
            if(ok == 0){
                queries[i].f = bounds[um[i+n]];
            }
            else{
                queries[i].s = bounds[um[i+n+m]];
            }
        }
    }
    int dfs(int src){
        v.eb(src);
        int val = sz(v) - 1;
        loc[src] = val;
        int r = val;
        f0r(i, ALPH){
            if(t[src][i] == -1) continue;
            int ret = dfs(t[src][i]);
            r = max(r, ret);
        }
        bounds[src] = mp(val, r);
        return r;
    }
};


Trie<VALS> f;
Trie<VALS> b;

unordered_map<int, int> xm;
unordered_map<int, int> ym;

SegBit<int> seg;
int main(){
    fast_io();
    cin >> n >> m;
    string temporary;
    getline(cin, temporary);
    f.build();
    b.build();
    int cnt = 0;
    f0r(i, n){
        string si;
        cin >> si;
        f.ins(si, cnt);
        reverse(all(si));
        b.ins(si, cnt);
        cnt++;
    }
    cnt = 0;
    f0r(i, m){
        string pi, qi;
        cin >> pi >> qi;
        f.ins(pi, cnt+n);
        reverse(all(qi));
        b.ins(qi, cnt+n + m);
        cnt++;
    }
    b.ok = 1;
    f.euler();
    b.euler();
    set<int> ycoords;
    set<int> xcoords;
    f0r(i, n){
        xcoords.insert(pts[i].f);
        ycoords.insert(pts[i].s);
    }
    f0r(i, m){
        xcoords.insert(queries[i].f.f); xcoords.insert(queries[i].f.s);
        ycoords.insert(queries[i].s.f); ycoords.insert(queries[i].s.s);
    }
    cnt = 1;
    for(auto x: xcoords){
        xm[x] = cnt;
        cnt++;
    }
    cnt = 1;
    for(auto x: ycoords){
        ym[x] = cnt;
        cnt++;
    }
    f0r(i, n){
        pts[i].f = xm[pts[i].f];
        pts[i].s = ym[pts[i].s];
        seg.upd(pts[i].f, pts[i].s, 1);
    }
    f0r(i, m){
        queries[i].f.f = xm[queries[i].f.f];
        queries[i].s.f = ym[queries[i].s.f];
        queries[i].f.s = xm[queries[i].f.s];
        queries[i].s.s = ym[queries[i].s.s];
        cout << seg.query(queries[i].f.f, queries[i].f.s, queries[i].s.f, queries[i].s.s) << endl;;
    }
    return 0;
}

Compilation message

selling_rna.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")
 
selling_rna.cpp: In function 'void io(std::__cxx11::string)':
selling_rna.cpp:50:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(FIN, "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~
selling_rna.cpp:51:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(FOUT, "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 106744 KB Output is correct
2 Correct 92 ms 106768 KB Output is correct
3 Correct 91 ms 106744 KB Output is correct
4 Correct 91 ms 106932 KB Output is correct
5 Correct 90 ms 106744 KB Output is correct
6 Correct 89 ms 106716 KB Output is correct
7 Correct 90 ms 106744 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 127116 KB Output is correct
2 Correct 284 ms 132396 KB Output is correct
3 Correct 268 ms 129944 KB Output is correct
4 Correct 276 ms 132172 KB Output is correct
5 Correct 354 ms 142260 KB Output is correct
6 Correct 356 ms 142488 KB Output is correct
7 Correct 157 ms 110388 KB Output is correct
8 Correct 296 ms 129780 KB Output is correct
9 Correct 263 ms 128340 KB Output is correct
10 Correct 216 ms 123648 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 116032 KB Output is correct
2 Correct 327 ms 114724 KB Output is correct
3 Correct 370 ms 115828 KB Output is correct
4 Correct 292 ms 113596 KB Output is correct
5 Correct 333 ms 114712 KB Output is correct
6 Correct 388 ms 115732 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 106744 KB Output is correct
2 Correct 92 ms 106768 KB Output is correct
3 Correct 91 ms 106744 KB Output is correct
4 Correct 91 ms 106932 KB Output is correct
5 Correct 90 ms 106744 KB Output is correct
6 Correct 89 ms 106716 KB Output is correct
7 Correct 90 ms 106744 KB Output is correct
8 Correct 239 ms 127116 KB Output is correct
9 Correct 284 ms 132396 KB Output is correct
10 Correct 268 ms 129944 KB Output is correct
11 Correct 276 ms 132172 KB Output is correct
12 Correct 354 ms 142260 KB Output is correct
13 Correct 356 ms 142488 KB Output is correct
14 Correct 157 ms 110388 KB Output is correct
15 Correct 296 ms 129780 KB Output is correct
16 Correct 263 ms 128340 KB Output is correct
17 Correct 216 ms 123648 KB Output is correct
18 Correct 374 ms 116032 KB Output is correct
19 Correct 327 ms 114724 KB Output is correct
20 Correct 370 ms 115828 KB Output is correct
21 Correct 292 ms 113596 KB Output is correct
22 Correct 333 ms 114712 KB Output is correct
23 Correct 388 ms 115732 KB Output is correct
24 Correct 490 ms 138276 KB Output is correct
25 Correct 666 ms 141096 KB Output is correct
26 Correct 351 ms 136404 KB Output is correct
27 Correct 428 ms 137560 KB Output is correct
28 Correct 1283 ms 139532 KB Output is correct
29 Correct 742 ms 129088 KB Output is correct