oj.uz

Submission #431398

# Submission time Handle Problem Language Result Execution time Memory
431398 2021-06-17T11:38:54 Z MarcoMeijer Selling RNA Strands (JOI16_selling_rna) C++14
60 / 100
 665 ms 49104 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 = 2e5;
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 13 ms 19148 KB Output is correct
2 Correct 14 ms 19148 KB Output is correct
3 Correct 13 ms 19116 KB Output is correct
4 Correct 13 ms 19112 KB Output is correct
5 Correct 13 ms 19120 KB Output is correct
6 Correct 14 ms 19148 KB Output is correct
7 Correct 13 ms 19148 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 31300 KB Output is correct
2 Correct 92 ms 32104 KB Output is correct
3 Correct 90 ms 31964 KB Output is correct
4 Correct 97 ms 31796 KB Output is correct
5 Correct 104 ms 27072 KB Output is correct
6 Correct 96 ms 27152 KB Output is correct
7 Correct 88 ms 34300 KB Output is correct
8 Correct 118 ms 35744 KB Output is correct
9 Correct 105 ms 35656 KB Output is correct
10 Correct 75 ms 29552 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 27956 KB Output is correct
2 Correct 127 ms 24280 KB Output is correct
3 Correct 166 ms 27064 KB Output is correct
4 Correct 118 ms 26472 KB Output is correct
5 Correct 137 ms 24184 KB Output is correct
6 Correct 167 ms 27024 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19148 KB Output is correct
2 Correct 14 ms 19148 KB Output is correct
3 Correct 13 ms 19116 KB Output is correct
4 Correct 13 ms 19112 KB Output is correct
5 Correct 13 ms 19120 KB Output is correct
6 Correct 14 ms 19148 KB Output is correct
7 Correct 13 ms 19148 KB Output is correct
8 Correct 85 ms 31300 KB Output is correct
9 Correct 92 ms 32104 KB Output is correct
10 Correct 90 ms 31964 KB Output is correct
11 Correct 97 ms 31796 KB Output is correct
12 Correct 104 ms 27072 KB Output is correct
13 Correct 96 ms 27152 KB Output is correct
14 Correct 88 ms 34300 KB Output is correct
15 Correct 118 ms 35744 KB Output is correct
16 Correct 105 ms 35656 KB Output is correct
17 Correct 75 ms 29552 KB Output is correct
18 Correct 173 ms 27956 KB Output is correct
19 Correct 127 ms 24280 KB Output is correct
20 Correct 166 ms 27064 KB Output is correct
21 Correct 118 ms 26472 KB Output is correct
22 Correct 137 ms 24184 KB Output is correct
23 Correct 167 ms 27024 KB Output is correct
24 Correct 156 ms 32844 KB Output is correct
25 Correct 284 ms 35596 KB Output is correct
26 Correct 131 ms 32988 KB Output is correct
27 Correct 217 ms 33044 KB Output is correct
28 Incorrect 665 ms 49104 KB Output isn't correct
29 Halted 0 ms 0 KB -