oj.uz

Submission #431400

# Submission time Handle Problem Language Result Execution time Memory
431400 2021-06-17T11:39:27 Z MarcoMeijer Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 596 ms 73220 KB 
#include <bits/stdc++.h>
using namespace std;
 
// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e18
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// input
template<class T> void IN(T& x) {cin >> x;}
template<class H, class... T> void IN(H& h, T&... t) {IN(h); IN(t...); }
 
// output
template<class T1, class T2> void OUT(const pair<T1,T2>& x);
template<class T> void OUT(const vector<T>& x);
template<class T> void OUT(const T& x) {cout << x;}
template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); }
template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi,' ',x.se);}
template<class T> void OUT(const vector<T>& x) {RE(i,x.size()) OUT(i==0?"":" ",x[i]);}
template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); }
template<class H> void OUTLS(const H& h) {OUTL(h); }
template<class H, class... T> void OUTLS(const H& h, const T&... t) {OUT(h,' '); OUTLS(t...); }
 
// dp
template<class T> bool ckmin(T&a, T&b) { bool bl = a > b; a = min(a,b); return bl;}
template<class T> bool ckmax(T&a, T&b) { bool bl = a < b; a = max(a,b); return bl;}
 
void program();
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    program();
}
 
 
// mod library
ll MOD=1e9+7;
 
inline ll mod(ll x_) {
    return (x_)%MOD;
}
ll modpow(ll x_, ll N_) {
    if(N_ == 0) return 1;
    ll a = modpow(x_,N_/2);
    a = (a*a)%MOD;
    if(N_%2) a = (a*x_)%MOD;
    return a;
}
ll inv(ll x_) {
    return modpow(x_, MOD-2);
}
class mi {
public:
    mi(ll v=0) {value = v;}
    mi  operator+ (ll rs) {return mod(value+rs);}
    mi  operator- (ll rs) {return mod(value-rs+MOD);}
    mi  operator* (ll rs) {return mod(value*rs);}
    mi  operator/ (ll rs) {return mod(value*inv(rs));}
    mi& operator+=(ll rs) {*this = (*this)+rs; return *this;}
    mi& operator-=(ll rs) {*this = (*this)-rs; return *this;}
    mi& operator*=(ll rs) {*this = (*this)*rs; return *this;}
    mi& operator/=(ll rs) {*this = (*this)/rs; return *this;}
    operator ll&() {return value;}
 
    ll value;
};
typedef vector<mi> vmi;
 
//===================//
//   begin program   //
//===================//
 
const int MX = 5e5;
const int N = (1<<23);
 
// debug
void printString(string s) {
    FOR(c,s) c+='a';
    OUTL(s);
}
 
// in and output
int n, m;
string s[MX], p[MX], q[MX];
int ans[MX];

// 2d problem
int x[MX], y[MX];
int bgx[MX], edx[MX], bgy[MX], edy[MX];

// fenwick tree
int FT[MX];
void addFT(int i, int value) {
    for(i++; i<MX; i+=i&-i) FT[i] += value;
}
int getFT(int i) {
    int ans = 0;
    for(i++; i; i-=i&-i) ans += FT[i];
    return ans;
}

typedef tuple<int,int,int> T;
 
void program() {
    // input
    IN(n,m);
    RE(i,n) IN(s[i]);
    RE(i,m) IN(p[i],q[i]);
 
    // compress strings
    map<char,char> charToComp;
    charToComp['A']=0, charToComp['U']=1, charToComp['G']=2, charToComp['C']=3;
    RE(i,n) FOR(c,s[i]) c = charToComp[c];
    RE(i,m) {
        FOR(c,p[i]) c = charToComp[c];
        FOR(c,q[i]) c = charToComp[c];
    }
 
    // will the coördinates
    RE(i,m) reverse(all(q[i]));
    RE(_,2) { // x
        vector<string> v;
        RE(i,n) v.pb(s[i]);
        RE(i,m) v.pb((_?q:p)[i]);
        sort(all(v));

        RE(i,n)
            (_?y:x)[i] = lower_bound(all(v),s[i]) - v.begin();
        
        RE(i,m) {
            (_?bgy:bgx)[i] = lower_bound(all(v),(_?q:p)[i]) - v.begin();
            (_?q:p)[i].back()++;
            (_?edy:edx)[i] = lower_bound(all(v),(_?q:p)[i]) - v.begin() - 1;
            (_?q:p)[i].back()--;
        }

        RE(i,n) reverse(all(s[i]));
    }

    // coördinate compression
    vi difx, dify;
    RE(i,n) difx.pb(x[i]), dify.pb(y[i]);
    RE(i,m) difx.pb(bgx[i]), difx.pb(edx[i]), dify.pb(bgy[i]), dify.pb(edy[i]);
    sort(all(difx)); sort(all(dify));
    RE(i,n) {
        x[i] = lower_bound(all(difx),x[i])-difx.begin();
        y[i] = lower_bound(all(dify),y[i])-dify.begin();
    }
    RE(i,m) {
        bgx[i] = lower_bound(all(difx),bgx[i])-difx.begin();
        edx[i] = lower_bound(all(difx),edx[i])-difx.begin();
        bgy[i] = lower_bound(all(dify),bgy[i])-dify.begin();
        edy[i] = lower_bound(all(dify),edy[i])-dify.begin();
    }

    // count points in rectangle
    priority_queue<T,vector<T>,greater<T>> pq;
    RE(i,m) pq.push({bgx[i],1,i});
    RE(i,n) pq.push({x  [i],2,i});
    RE(i,m) pq.push({edx[i],3,i});
    while(!pq.empty()) {
        T p = pq.top(); pq.pop();
        int a, t, b, i;
        tie(a,t,i) = p;
        if(t == 1) {
            ans[i] -= getFT(edy[i]) - getFT(bgy[i]-1);
        }
        if(t == 2) {
            addFT(y[i],1);
        }
        if(t == 3) {
            ans[i] += getFT(edy[i]) - getFT(bgy[i]-1);
        }
    }

    // output
    RE(i,m) OUTL(ans[i]);
}

Compilation message

selling_rna.cpp: In function 'void program()':
selling_rna.cpp:185:19: warning: unused variable 'b' [-Wunused-variable]
  185 |         int a, t, b, i;
      |                   ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47280 KB Output is correct
2 Correct 30 ms 47424 KB Output is correct
3 Correct 27 ms 47300 KB Output is correct
4 Correct 29 ms 47304 KB Output is correct
5 Correct 35 ms 47392 KB Output is correct
6 Correct 30 ms 47308 KB Output is correct
7 Correct 29 ms 47308 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 55604 KB Output is correct
2 Correct 107 ms 56372 KB Output is correct
3 Correct 115 ms 56260 KB Output is correct
4 Correct 113 ms 56056 KB Output is correct
5 Correct 101 ms 52852 KB Output is correct
6 Correct 100 ms 52980 KB Output is correct
7 Correct 88 ms 57124 KB Output is correct
8 Correct 117 ms 58228 KB Output is correct
9 Correct 127 ms 58000 KB Output is correct
10 Correct 92 ms 54340 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 55748 KB Output is correct
2 Correct 155 ms 52180 KB Output is correct
3 Correct 197 ms 54832 KB Output is correct
4 Correct 134 ms 54264 KB Output is correct
5 Correct 148 ms 52044 KB Output is correct
6 Correct 199 ms 54832 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47280 KB Output is correct
2 Correct 30 ms 47424 KB Output is correct
3 Correct 27 ms 47300 KB Output is correct
4 Correct 29 ms 47304 KB Output is correct
5 Correct 35 ms 47392 KB Output is correct
6 Correct 30 ms 47308 KB Output is correct
7 Correct 29 ms 47308 KB Output is correct
8 Correct 105 ms 55604 KB Output is correct
9 Correct 107 ms 56372 KB Output is correct
10 Correct 115 ms 56260 KB Output is correct
11 Correct 113 ms 56056 KB Output is correct
12 Correct 101 ms 52852 KB Output is correct
13 Correct 100 ms 52980 KB Output is correct
14 Correct 88 ms 57124 KB Output is correct
15 Correct 117 ms 58228 KB Output is correct
16 Correct 127 ms 58000 KB Output is correct
17 Correct 92 ms 54340 KB Output is correct
18 Correct 163 ms 55748 KB Output is correct
19 Correct 155 ms 52180 KB Output is correct
20 Correct 197 ms 54832 KB Output is correct
21 Correct 134 ms 54264 KB Output is correct
22 Correct 148 ms 52044 KB Output is correct
23 Correct 199 ms 54832 KB Output is correct
24 Correct 163 ms 57040 KB Output is correct
25 Correct 264 ms 59572 KB Output is correct
26 Correct 134 ms 57304 KB Output is correct
27 Correct 161 ms 57268 KB Output is correct
28 Correct 596 ms 73220 KB Output is correct
29 Correct 505 ms 67864 KB Output is correct