Submission #1109547

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109547		flyingkite	Index (COCI21_index)	C++17	110 / 110	436 ms	24980 KiB

index

#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 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50