oj.uz

Submission #894324

# Submission time Handle Problem Language Result Execution time Memory
894324 2023-12-28T05:29:32 Z vjudge1 Index (COCI21_index) C++11
110 / 110
 1400 ms 67864 KB 
#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
using namespace std;
#define F first
#define S second
typedef long long ll;
#define pii pair <int, int>
#define pll pair <ll, ll>
typedef long double ld;
const ll N = 2 * 1e5 + 10, M = 6 * 1e6 + 10;
const ll mod = 1e9 + 7;

ll um(ll a, ll b){
	return ((1LL * a * b) % mod + mod) % mod;
}
ll subr(ll a, ll b){
	return ((1LL * a - b) % mod + mod) % mod;
}
ll add(ll a, ll b){
	return ((1LL * a + b) % mod + mod) % mod;
}
ll binpow(ll x, ll step){
	ll res = 1LL;
	while(step){
		if(step & 1) res = um(res, x);
		x = um(x, x);
		step /= 2;
	}
	return res;
}
/*
	Восемь восемьсот пять пять пять
	три пять три пять
	Проще кому то позвонить
	чем у кого-то деньги занимать
*/
int l[M], r[M], timer, p[N];
vector <int> vec[N];
int tree[M], sz = 262144;

int build(int lx, int rx){
	int v = timer++;
	if(rx - lx == 1) return v;
	int mid = (rx + lx) / 2;
	l[v] = build(lx, mid);
	r[v] = build(mid, rx);
	return v;
}
int cope(int x){
	int v = timer++;
	l[v] = l[x];
	r[v] = r[x];
	return v;
}
int upd(int i, int x, int lx, int rx){
	int v = cope(x);
	if(rx - lx == 1){
		tree[v] = 1;
		return v;
	}
	int mid = (rx + lx) / 2;
	if(i < mid) l[v] = upd(i, l[x], lx, mid);
	else r[v] = upd(i, r[x], mid, rx);
	tree[v] = tree[l[v]] + tree[r[v]];
	return v;
}
int get(int from, int to, int x1, int x2, int lx, int rx){
	if(from >= rx || lx >= to) return 0;
	if(from <= lx && rx <= to) return tree[x1] - tree[x2];
	int mid = (lx + rx) / 2;
	int s1 = get(from, to, l[x1], l[x2], lx, mid);
	int s2 = get(from, to, r[x1], r[x2], mid, rx);
	return s1 + s2;
}
int main() {
	ios::sync_with_stdio(false);
  	cin.tie(NULL);
  	int n, q, last = 200000;
  	cin >> n >> q;
  	for(int i = 0, x; i < n; i++){
  		cin >> x;
  		vec[x].pb(i);
  	}
  	p[0] = build(0, sz);
  	for(int i = 1; i <= last; i++){
  		int pred = p[i - 1];
  		for(auto u : vec[i]){
  			pred = upd(u, pred, 0, sz);
  		}
  		p[i] = pred;
  	}
  	for(int i = 0, from, to; i < q; i++){
  		cin >> from >> to;
  		int lx = 1, rx = last + 5;
  		while(rx - lx > 1){
  			int mid = (rx + lx) / 2;
  			if(get(from - 1, to, p[last], p[mid - 1], 0, sz) >= mid) lx = mid;
  			else rx = mid;
  		}
  		cout << lx << endl;
  	}
  return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16732 KB Output is correct
2 Correct 8 ms 16732 KB Output is correct
3 Correct 10 ms 16732 KB Output is correct
4 Correct 9 ms 16728 KB Output is correct
5 Correct 9 ms 16652 KB Output is correct
6 Correct 9 ms 16728 KB Output is correct
7 Correct 9 ms 16732 KB Output is correct
8 Correct 8 ms 16732 KB Output is correct
9 Correct 10 ms 16732 KB Output is correct
10 Correct 9 ms 16824 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16732 KB Output is correct
2 Correct 8 ms 16732 KB Output is correct
3 Correct 10 ms 16732 KB Output is correct
4 Correct 9 ms 16728 KB Output is correct
5 Correct 9 ms 16652 KB Output is correct
6 Correct 9 ms 16728 KB Output is correct
7 Correct 9 ms 16732 KB Output is correct
8 Correct 8 ms 16732 KB Output is correct
9 Correct 10 ms 16732 KB Output is correct
10 Correct 9 ms 16824 KB Output is correct
11 Correct 270 ms 28168 KB Output is correct
12 Correct 259 ms 28240 KB Output is correct
13 Correct 266 ms 28636 KB Output is correct
14 Correct 257 ms 28244 KB Output is correct
15 Correct 261 ms 28240 KB Output is correct
16 Correct 263 ms 28244 KB Output is correct
17 Correct 269 ms 28204 KB Output is correct
18 Correct 268 ms 28736 KB Output is correct
19 Correct 268 ms 28384 KB Output is correct
20 Correct 283 ms 28496 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16732 KB Output is correct
2 Correct 8 ms 16732 KB Output is correct
3 Correct 10 ms 16732 KB Output is correct
4 Correct 9 ms 16728 KB Output is correct
5 Correct 9 ms 16652 KB Output is correct
6 Correct 9 ms 16728 KB Output is correct
7 Correct 9 ms 16732 KB Output is correct
8 Correct 8 ms 16732 KB Output is correct
9 Correct 10 ms 16732 KB Output is correct
10 Correct 9 ms 16824 KB Output is correct
11 Correct 270 ms 28168 KB Output is correct
12 Correct 259 ms 28240 KB Output is correct
13 Correct 266 ms 28636 KB Output is correct
14 Correct 257 ms 28244 KB Output is correct
15 Correct 261 ms 28240 KB Output is correct
16 Correct 263 ms 28244 KB Output is correct
17 Correct 269 ms 28204 KB Output is correct
18 Correct 268 ms 28736 KB Output is correct
19 Correct 268 ms 28384 KB Output is correct
20 Correct 283 ms 28496 KB Output is correct
21 Correct 1298 ms 67372 KB Output is correct
22 Correct 1266 ms 67168 KB Output is correct
23 Correct 1369 ms 66964 KB Output is correct
24 Correct 1309 ms 67372 KB Output is correct
25 Correct 1357 ms 67192 KB Output is correct
26 Correct 1379 ms 66968 KB Output is correct
27 Correct 1384 ms 67424 KB Output is correct
28 Correct 1369 ms 67864 KB Output is correct
29 Correct 1400 ms 67168 KB Output is correct
30 Correct 1307 ms 67176 KB Output is correct