oj.uz

Submission #431402

# Submission time Handle Problem Language Result Execution time Memory
431402 2021-06-17T11:41:21 Z MarcoMeijer Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 591 ms 73752 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);
 
// 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]);
 
    // will the coördinates
    RE(i,m) reverse(all(q[i]));
    RE(_,2) {
        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:170:19: warning: unused variable 'b' [-Wunused-variable]
  170 |         int a, t, b, i;
      |                   ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47336 KB Output is correct
2 Correct 30 ms 47380 KB Output is correct
3 Correct 30 ms 47288 KB Output is correct
4 Correct 29 ms 47404 KB Output is correct
5 Correct 33 ms 47328 KB Output is correct
6 Correct 29 ms 47384 KB Output is correct
7 Correct 28 ms 47396 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 55608 KB Output is correct
2 Correct 73 ms 56396 KB Output is correct
3 Correct 73 ms 56272 KB Output is correct
4 Correct 81 ms 56004 KB Output is correct
5 Correct 68 ms 52776 KB Output is correct
6 Correct 71 ms 52864 KB Output is correct
7 Correct 75 ms 57112 KB Output is correct
8 Correct 89 ms 58052 KB Output is correct
9 Correct 102 ms 58096 KB Output is correct
10 Correct 72 ms 54336 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 55672 KB Output is correct
2 Correct 145 ms 52084 KB Output is correct
3 Correct 159 ms 54768 KB Output is correct
4 Correct 131 ms 54216 KB Output is correct
5 Correct 143 ms 52060 KB Output is correct
6 Correct 187 ms 54788 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47336 KB Output is correct
2 Correct 30 ms 47380 KB Output is correct
3 Correct 30 ms 47288 KB Output is correct
4 Correct 29 ms 47404 KB Output is correct
5 Correct 33 ms 47328 KB Output is correct
6 Correct 29 ms 47384 KB Output is correct
7 Correct 28 ms 47396 KB Output is correct
8 Correct 56 ms 55608 KB Output is correct
9 Correct 73 ms 56396 KB Output is correct
10 Correct 73 ms 56272 KB Output is correct
11 Correct 81 ms 56004 KB Output is correct
12 Correct 68 ms 52776 KB Output is correct
13 Correct 71 ms 52864 KB Output is correct
14 Correct 75 ms 57112 KB Output is correct
15 Correct 89 ms 58052 KB Output is correct
16 Correct 102 ms 58096 KB Output is correct
17 Correct 72 ms 54336 KB Output is correct
18 Correct 179 ms 55672 KB Output is correct
19 Correct 145 ms 52084 KB Output is correct
20 Correct 159 ms 54768 KB Output is correct
21 Correct 131 ms 54216 KB Output is correct
22 Correct 143 ms 52060 KB Output is correct
23 Correct 187 ms 54788 KB Output is correct
24 Correct 138 ms 57044 KB Output is correct
25 Correct 214 ms 59592 KB Output is correct
26 Correct 113 ms 57088 KB Output is correct
27 Correct 149 ms 57656 KB Output is correct
28 Correct 591 ms 73752 KB Output is correct
29 Correct 540 ms 64684 KB Output is correct