oj.uz

Submission #1109547

# Submission time Handle Problem Language Result Execution time Memory
1109547 2024-11-07T03:14:03 Z flyingkite Index (COCI21_index) C++17
110 / 110
 436 ms 24980 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()
 
const ll N = 2e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 450;
ll n,q;
ll a[N], res[N], L[N], R[N], tot[N];
vector<ll>t[N];
struct fenwick_tree{
	ll n;
	vector<ll>ft;
	void init(ll _n){
		n = _n;
		ft.clear(); ft.resize(n + 10);
	}
	void update(ll idx, ll val){
		while(idx <= n) ft[idx] += val, idx += (idx & (-idx));
	}
	ll get(ll idx){
		ll res = 0;
		while(idx > 0) res += ft[idx], idx -= (idx & (-idx));
		return res;
	}
} ft;
void para_bs(){
    ft.init(2e5);
    for(int i = 1; i <= q;i++) tot[i] = 0;
    for(int i = 1; i <= n;i++){
        ft.update(a[i], 1);
        for(auto x : t[i]){ 
            ll j = abs(x);
            if(L[j] > R[j]) continue;
            ll mid = (L[j] + R[j]) / 2;
            if(x < 0) tot[j] -= ft.get(2e5) - ft.get(mid - 1);
            else{
                if(L[j] > R[j]) continue;
                tot[j] += ft.get(2e5) - ft.get(mid - 1);
                if(tot[j] >= mid){
                    res[j] = mid;
                    L[j] = mid + 1;
                }
                else R[j] = mid - 1;
            }
        }   
    }
}
void to_thic_cau(){
    cin >> n >> q;
    for(int i = 1; i <= n;i++) cin >> a[i];
    for(int i = 1; i <= q;i++){
        ll l,r; cin >> l >> r;
        t[r].pb(i); t[l - 1].pb(-i);
        L[i] = 1, R[i] = 2e5;
    }
    for(int i = 1; i <= 20;i++) para_bs();
    for(int i = 1; i <= q;i++) cout << res[i] << '\n';
}    
 
signed main()   
{  
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll tc = 1;
    //cin >> tc;
    while(tc--) to_thic_cau();
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14416 KB Output is correct
2 Correct 6 ms 14492 KB Output is correct
3 Correct 5 ms 14416 KB Output is correct
4 Correct 6 ms 14416 KB Output is correct
5 Correct 5 ms 14388 KB Output is correct
6 Correct 5 ms 14416 KB Output is correct
7 Correct 5 ms 14416 KB Output is correct
8 Correct 6 ms 14416 KB Output is correct
9 Correct 6 ms 14416 KB Output is correct
10 Correct 5 ms 14416 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14416 KB Output is correct
2 Correct 6 ms 14492 KB Output is correct
3 Correct 5 ms 14416 KB Output is correct
4 Correct 6 ms 14416 KB Output is correct
5 Correct 5 ms 14388 KB Output is correct
6 Correct 5 ms 14416 KB Output is correct
7 Correct 5 ms 14416 KB Output is correct
8 Correct 6 ms 14416 KB Output is correct
9 Correct 6 ms 14416 KB Output is correct
10 Correct 5 ms 14416 KB Output is correct
11 Correct 81 ms 17000 KB Output is correct
12 Correct 81 ms 16968 KB Output is correct
13 Correct 82 ms 16972 KB Output is correct
14 Correct 86 ms 16968 KB Output is correct
15 Correct 89 ms 16976 KB Output is correct
16 Correct 79 ms 16968 KB Output is correct
17 Correct 82 ms 17004 KB Output is correct
18 Correct 79 ms 17032 KB Output is correct
19 Correct 80 ms 16968 KB Output is correct
20 Correct 79 ms 16968 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14416 KB Output is correct
2 Correct 6 ms 14492 KB Output is correct
3 Correct 5 ms 14416 KB Output is correct
4 Correct 6 ms 14416 KB Output is correct
5 Correct 5 ms 14388 KB Output is correct
6 Correct 5 ms 14416 KB Output is correct
7 Correct 5 ms 14416 KB Output is correct
8 Correct 6 ms 14416 KB Output is correct
9 Correct 6 ms 14416 KB Output is correct
10 Correct 5 ms 14416 KB Output is correct
11 Correct 81 ms 17000 KB Output is correct
12 Correct 81 ms 16968 KB Output is correct
13 Correct 82 ms 16972 KB Output is correct
14 Correct 86 ms 16968 KB Output is correct
15 Correct 89 ms 16976 KB Output is correct
16 Correct 79 ms 16968 KB Output is correct
17 Correct 82 ms 17004 KB Output is correct
18 Correct 79 ms 17032 KB Output is correct
19 Correct 80 ms 16968 KB Output is correct
20 Correct 79 ms 16968 KB Output is correct
21 Correct 393 ms 24904 KB Output is correct
22 Correct 361 ms 24904 KB Output is correct
23 Correct 386 ms 24980 KB Output is correct
24 Correct 362 ms 24904 KB Output is correct
25 Correct 436 ms 24904 KB Output is correct
26 Correct 433 ms 24904 KB Output is correct
27 Correct 394 ms 24876 KB Output is correct
28 Correct 403 ms 24856 KB Output is correct
29 Correct 400 ms 24908 KB Output is correct
30 Correct 397 ms 24904 KB Output is correct