oj.uz

Submission #153615

# Submission time Handle Problem Language Result Execution time Memory
153615 2019-09-15T03:19:14 Z 12tqian Selling RNA Strands (JOI16_selling_rna) C++14
60 / 100
 1500 ms 144660 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;
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, 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;

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 81 ms 94552 KB Output is correct
2 Correct 79 ms 94556 KB Output is correct
3 Correct 79 ms 94584 KB Output is correct
4 Correct 79 ms 94456 KB Output is correct
5 Correct 80 ms 94568 KB Output is correct
6 Correct 79 ms 94516 KB Output is correct
7 Correct 79 ms 94584 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 118132 KB Output is correct
2 Correct 304 ms 127360 KB Output is correct
3 Correct 271 ms 122500 KB Output is correct
4 Correct 290 ms 127048 KB Output is correct
5 Correct 367 ms 140892 KB Output is correct
6 Correct 377 ms 141264 KB Output is correct
7 Correct 150 ms 99680 KB Output is correct
8 Correct 273 ms 125464 KB Output is correct
9 Correct 284 ms 123960 KB Output is correct
10 Correct 232 ms 116424 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 103828 KB Output is correct
2 Correct 348 ms 103464 KB Output is correct
3 Correct 423 ms 104204 KB Output is correct
4 Correct 275 ms 101268 KB Output is correct
5 Correct 355 ms 103872 KB Output is correct
6 Correct 399 ms 104700 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 94552 KB Output is correct
2 Correct 79 ms 94556 KB Output is correct
3 Correct 79 ms 94584 KB Output is correct
4 Correct 79 ms 94456 KB Output is correct
5 Correct 80 ms 94568 KB Output is correct
6 Correct 79 ms 94516 KB Output is correct
7 Correct 79 ms 94584 KB Output is correct
8 Correct 236 ms 118132 KB Output is correct
9 Correct 304 ms 127360 KB Output is correct
10 Correct 271 ms 122500 KB Output is correct
11 Correct 290 ms 127048 KB Output is correct
12 Correct 367 ms 140892 KB Output is correct
13 Correct 377 ms 141264 KB Output is correct
14 Correct 150 ms 99680 KB Output is correct
15 Correct 273 ms 125464 KB Output is correct
16 Correct 284 ms 123960 KB Output is correct
17 Correct 232 ms 116424 KB Output is correct
18 Correct 365 ms 103828 KB Output is correct
19 Correct 348 ms 103464 KB Output is correct
20 Correct 423 ms 104204 KB Output is correct
21 Correct 275 ms 101268 KB Output is correct
22 Correct 355 ms 103872 KB Output is correct
23 Correct 399 ms 104700 KB Output is correct
24 Correct 486 ms 141520 KB Output is correct
25 Correct 734 ms 144660 KB Output is correct
26 Correct 415 ms 139664 KB Output is correct
27 Correct 460 ms 140788 KB Output is correct
28 Execution timed out 1554 ms 141192 KB Time limit exceeded
29 Halted 0 ms 0 KB -