Submission #793133

#	Time	Username	Problem	Language	Result	Execution time	Memory
793133		hafo	Index (COCI21_index)	C++14	60 / 110	2552 ms	48380 KiB

index

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 2e5 + 7;
const ll oo = 1e18 + 69;

int n, q, a[maxn], u, v;

struct ST {
    struct node {
        vector<int> x;
        friend node operator + (node &a, node &b) {
            node c;
            int i = 0, j = 0;
            while(i < Size(a.x) || j < Size(b.x)) {
                if(j == Size(b.x) || (i != Size(a.x) && a.x[i] < b.x[j])) c.x.pb(a.x[i++]);
                else c.x.pb(b.x[j++]);
            }
            return c;
        }
    };

    node st[4 * maxn];

    void build(int id, int l, int r) {
        if(l == r) {
            st[id].x.pb(a[l]);
            return;
        }
        int mid = l + r >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
        st[id] = st[id << 1] + st[id << 1 | 1];
    }

    int get(int id, int l, int r, int u, int v, int x) {
        if(r < u || l > v) return 0;
        if(u <= l && r <= v) {
            int idd = lower_bound(all(st[id].x), x) - st[id].x.begin();
            return Size(st[id].x) - idd;
        }
        int mid = l + r >> 1;
        return get(id << 1, l, mid, u, v, x) + get(id << 1 | 1, mid + 1, r, u, v, x);
    }

} st;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    cin>>n>>q;
    for(int i = 1; i <= n; i++) cin>>a[i];
    st.build(1, 1, n);
    
    while(q--) {
        cin>>u>>v;
        int l = 1, r = (v - u + 1), res = 0, mid;
        while(l <= r) {
            mid = l + r >> 1;
            if(st.get(1, 1, n, u, v, mid) >= mid) {
                res = mid;
                l = mid + 1;
            } else r = mid - 1;
        }
        cout<<res<<"\n";
    }
    return 0;
}

Compilation message (stderr)

index.cpp: In member function 'void ST::build(int, int, int)':
index.cpp:45:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |         int mid = l + r >> 1;
      |                   ~~^~~
index.cpp: In member function 'int ST::get(int, int, int, int, int, int)':
index.cpp:57:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |         int mid = l + r >> 1;
      |                   ~~^~~
index.cpp: In function 'int main()':
index.cpp:78:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |             mid = l + r >> 1;
      |                   ~~^~~

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 0 / 50