oj.uz

Submission #894323

# Submission time Handle Problem Language Result Execution time Memory
894323 2023-12-28T05:29:02 Z vjudge1 Index (COCI21_index) C++11
60 / 110
 286 ms 66944 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 = 2 * 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 16728 KB Output is correct
2 Correct 8 ms 16732 KB Output is correct
3 Correct 8 ms 16728 KB Output is correct
4 Correct 8 ms 16732 KB Output is correct
5 Correct 9 ms 16732 KB Output is correct
6 Correct 8 ms 16732 KB Output is correct
7 Correct 8 ms 16732 KB Output is correct
8 Correct 8 ms 16732 KB Output is correct
9 Correct 8 ms 16732 KB Output is correct
10 Correct 8 ms 16984 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16728 KB Output is correct
2 Correct 8 ms 16732 KB Output is correct
3 Correct 8 ms 16728 KB Output is correct
4 Correct 8 ms 16732 KB Output is correct
5 Correct 9 ms 16732 KB Output is correct
6 Correct 8 ms 16732 KB Output is correct
7 Correct 8 ms 16732 KB Output is correct
8 Correct 8 ms 16732 KB Output is correct
9 Correct 8 ms 16732 KB Output is correct
10 Correct 8 ms 16984 KB Output is correct
11 Correct 264 ms 30440 KB Output is correct
12 Correct 268 ms 30460 KB Output is correct
13 Correct 276 ms 30212 KB Output is correct
14 Correct 259 ms 30444 KB Output is correct
15 Correct 264 ms 30800 KB Output is correct
16 Correct 266 ms 30292 KB Output is correct
17 Correct 264 ms 30292 KB Output is correct
18 Correct 276 ms 30412 KB Output is correct
19 Correct 263 ms 30292 KB Output is correct
20 Correct 286 ms 30396 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16728 KB Output is correct
2 Correct 8 ms 16732 KB Output is correct
3 Correct 8 ms 16728 KB Output is correct
4 Correct 8 ms 16732 KB Output is correct
5 Correct 9 ms 16732 KB Output is correct
6 Correct 8 ms 16732 KB Output is correct
7 Correct 8 ms 16732 KB Output is correct
8 Correct 8 ms 16732 KB Output is correct
9 Correct 8 ms 16732 KB Output is correct
10 Correct 8 ms 16984 KB Output is correct
11 Correct 264 ms 30440 KB Output is correct
12 Correct 268 ms 30460 KB Output is correct
13 Correct 276 ms 30212 KB Output is correct
14 Correct 259 ms 30444 KB Output is correct
15 Correct 264 ms 30800 KB Output is correct
16 Correct 266 ms 30292 KB Output is correct
17 Correct 264 ms 30292 KB Output is correct
18 Correct 276 ms 30412 KB Output is correct
19 Correct 263 ms 30292 KB Output is correct
20 Correct 286 ms 30396 KB Output is correct
21 Runtime error 77 ms 66944 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -