oj.uz

Submission #312711

# Submission time Handle Problem Language Result Execution time Memory
312711 2020-10-14T08:24:09 Z jainbot27 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 495 ms 42464 KB 
#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()

#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)

using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;

template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const char nl = '\n';
const int mxN = 1e5 + 10;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;
// IMPL FROM KACTL
int LB, RB;
struct Tree {
	using T = int;
	using U = vector<int>;
	vector<U> vals; int n;
	Tree(int n = 0) : vals(2*n), n(n) {}
	int qry(int pos){
		return lower_bound(all(vals[pos]), RB) - lower_bound(all(vals[pos]), LB);
	}
	void update(int pos, T val) {
		for (pos+=n; pos ; pos/=2){
			vals[pos].pb(val);
		}
	}
	void normalize(){
		trav(x, vals){
			sort(all(x));
		}
	}
	T query(int b, int e) { // query [b, e)
		T ans = 0;
		for (b += n, e += n; b < e; b /= 2, e /= 2) {
			if( b % 2 ) ans += qry(b++);
			if( e % 2 ) ans += qry(--e);
		}
		return ans;
	}
};
int n, m; 
string s[mxN], p[mxN], q[mxN];
int lba[mxN], uba[mxN], lbb[mxN], ubb[mxN], pos[mxN];
vector<pair<string, int>> tot;
int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
	Tree seg(n);
    F0R(i, n){
        cin >> s[i];
    }
    sort(s, s+n);
    F0R(i, m){
		cin >> p[i] >> q[i];
		reverse(all(q[i]));
		lba[i] = lower_bound(s, s+n, p[i])- s;
		p[i].back()++;
		uba[i] = lower_bound(s, s+n, p[i]) -s;
		// cout << lba[i] << ' ' << uba[i] << nl;
    }
	F0R(i, n){
		reverse(all(s[i]));
		tot.pb({s[i], i});
	}
	sort(all(tot));
	sort(s, s+n);
	F0R(i, n) assert(s[i] == tot[i].f);
	F0R(i, m){
		lbb[i] = lower_bound(s, s+n, q[i])-s;
		q[i].back()++;
		ubb[i] = lower_bound(s, s+n, q[i])-s;
		// cout << lbb[i] << ' ' << ubb[i] << nl;
	}
	F0R(i, n){
		pos[tot[i].s] = i;
	}
	F0R(i, n){
		seg.update(i, pos[i]);
	}
	seg.normalize();
	F0R(i, m){
		LB = lbb[i], RB = ubb[i];
		cout << seg.query(lba[i], uba[i]) << nl;
	}
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 7 ms 9728 KB Output is correct
4 Correct 7 ms 9728 KB Output is correct
5 Correct 7 ms 9728 KB Output is correct
6 Correct 7 ms 9728 KB Output is correct
7 Correct 7 ms 9728 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 16376 KB Output is correct
2 Correct 47 ms 19156 KB Output is correct
3 Correct 42 ms 18808 KB Output is correct
4 Correct 48 ms 19156 KB Output is correct
5 Correct 38 ms 16980 KB Output is correct
6 Correct 38 ms 16988 KB Output is correct
7 Correct 40 ms 19576 KB Output is correct
8 Correct 55 ms 21204 KB Output is correct
9 Correct 53 ms 21208 KB Output is correct
10 Correct 40 ms 18772 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 21096 KB Output is correct
2 Correct 98 ms 16876 KB Output is correct
3 Correct 119 ms 19044 KB Output is correct
4 Correct 87 ms 17684 KB Output is correct
5 Correct 85 ms 16748 KB Output is correct
6 Correct 110 ms 19176 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 7 ms 9728 KB Output is correct
4 Correct 7 ms 9728 KB Output is correct
5 Correct 7 ms 9728 KB Output is correct
6 Correct 7 ms 9728 KB Output is correct
7 Correct 7 ms 9728 KB Output is correct
8 Correct 29 ms 16376 KB Output is correct
9 Correct 47 ms 19156 KB Output is correct
10 Correct 42 ms 18808 KB Output is correct
11 Correct 48 ms 19156 KB Output is correct
12 Correct 38 ms 16980 KB Output is correct
13 Correct 38 ms 16988 KB Output is correct
14 Correct 40 ms 19576 KB Output is correct
15 Correct 55 ms 21204 KB Output is correct
16 Correct 53 ms 21208 KB Output is correct
17 Correct 40 ms 18772 KB Output is correct
18 Correct 130 ms 21096 KB Output is correct
19 Correct 98 ms 16876 KB Output is correct
20 Correct 119 ms 19044 KB Output is correct
21 Correct 87 ms 17684 KB Output is correct
22 Correct 85 ms 16748 KB Output is correct
23 Correct 110 ms 19176 KB Output is correct
24 Correct 98 ms 20708 KB Output is correct
25 Correct 158 ms 21648 KB Output is correct
26 Correct 74 ms 20372 KB Output is correct
27 Correct 88 ms 20752 KB Output is correct
28 Correct 495 ms 42464 KB Output is correct
29 Correct 335 ms 34944 KB Output is correct