oj.uz

Submission #153613

# Submission time Handle Problem Language Result Execution time Memory
153613 2019-09-15T03:00:24 Z 12tqian Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 472 ms 172048 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;
const int INF = 1e9;
const int MOD = 1e9 + 7;

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<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, m){
            if(ok == 0){
                pts[i].f = loc[um[i]];
                queries[i].f = bounds[um[i+n]];
            }
            else{
                pts[i].s = loc[um[i]];
                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;
    }
};
template<int LEN> struct mstree {
    Tree<pii> val[LEN+1]; // for offline queries use vector with binary search instead

    void upd(int x, int y, int t = 1) { // x-coordinate between 1 and SZ inclusive
        for (int X = x; X <= SZ; X += X&-X) {
            if (t == 1) val[X].insert({y,x});
            else val[X].erase({y,x});
        }
    }

    int query(int x, int y) {
        int t = 0;
        for (;x > 0; x -= x&-x) t += val[x].order_of_key({y,MOD});
        return t;
    }

    int query(int lox, int hix, int loy, int hiy) { // query number of elements within a rectangle
        return query(hix,hiy)-query(lox-1,hiy)
            -query(hix,loy-1)+query(lox-1,loy-1);
    }
};


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

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

mstree<3*MAX> ms;
Node<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 123 ms 122684 KB Output is correct
2 Correct 116 ms 122692 KB Output is correct
3 Correct 119 ms 122744 KB Output is correct
4 Correct 131 ms 122768 KB Output is correct
5 Correct 116 ms 122744 KB Output is correct
6 Correct 121 ms 122744 KB Output is correct
7 Correct 123 ms 122808 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 146232 KB Output is correct
2 Correct 369 ms 159392 KB Output is correct
3 Correct 314 ms 154580 KB Output is correct
4 Correct 345 ms 159316 KB Output is correct
5 Correct 412 ms 171700 KB Output is correct
6 Correct 414 ms 172048 KB Output is correct
7 Correct 192 ms 133240 KB Output is correct
8 Correct 313 ms 159500 KB Output is correct
9 Correct 309 ms 158136 KB Output is correct
10 Correct 278 ms 147944 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 131988 KB Output is correct
2 Correct 392 ms 131996 KB Output is correct
3 Correct 472 ms 132812 KB Output is correct
4 Incorrect 347 ms 129816 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 122684 KB Output is correct
2 Correct 116 ms 122692 KB Output is correct
3 Correct 119 ms 122744 KB Output is correct
4 Correct 131 ms 122768 KB Output is correct
5 Correct 116 ms 122744 KB Output is correct
6 Correct 121 ms 122744 KB Output is correct
7 Correct 123 ms 122808 KB Output is correct
8 Correct 300 ms 146232 KB Output is correct
9 Correct 369 ms 159392 KB Output is correct
10 Correct 314 ms 154580 KB Output is correct
11 Correct 345 ms 159316 KB Output is correct
12 Correct 412 ms 171700 KB Output is correct
13 Correct 414 ms 172048 KB Output is correct
14 Correct 192 ms 133240 KB Output is correct
15 Correct 313 ms 159500 KB Output is correct
16 Correct 309 ms 158136 KB Output is correct
17 Correct 278 ms 147944 KB Output is correct
18 Correct 411 ms 131988 KB Output is correct
19 Correct 392 ms 131996 KB Output is correct
20 Correct 472 ms 132812 KB Output is correct
21 Incorrect 347 ms 129816 KB Output isn't correct
22 Halted 0 ms 0 KB -