Submission #942565

#	Time	Username	Problem	Language	Result	Execution time	Memory
942565		vjudge1	Index (COCI21_index)	C++17	60 / 110	2537 ms	66736 KiB

index

#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("popcnt")
#pragma GCC target("avx,avx2,sse3,ssse3,sse4.1,sse4.2,tune=native")
#pragma GCC optimize(3)
#pragma GCC optimize("O3")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")

using namespace std;

using ld = long double;
using ll = long long;

#define int ll

#define sz(x) (int)x.size()

const int N = 2e5+5;
int n, q;
int p[N];

vector<int> T[4*N];

void init(int i, int tl, int tr){
    if(tl == tr){
        T[i].push_back(p[tl]);
        return;
    }

    int m = (tl + tr) / 2;

    init(2*i+1, tl, m);
    init(2*i+2, m+1, tr);

    merge(T[2*i+1].begin(), T[2*i+1].end(), T[2*i+2].begin(), T[2*i+2].end(), back_inserter(T[i]));

}

int query(int l, int r, int k, int i, int tl, int tr){
    if(r < tl or l > tr){
        return 0;
    }
    if(l <= tl && tr <= r){
        return lower_bound(T[i].begin(), T[i].end(), k) - T[i].begin();
    }
    int m = (tl + tr) / 2;
    return query(l, r, k, 2*i+1, tl, m) + query(l, r, k, 2*i+2, m+1, tr);
}

int query(int l, int r, int k){
    return query(l, r, k, 0, 0, n-1);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> q;
    for(int i=0; i<n; ++i){
        cin >> p[i];
    }

    init(0, 0, n-1);

    while(q--){
        int l, r;
        cin >> l >> r;
        l--, r--;

        int low = 1, high = r - l + 1;
        int res = 1;
        while(low <= high){
            int mid = (low + high) / 2;

            int tmp = r - l + 1 - query(l, r, mid);

            if(tmp >= mid){
                res = mid;
                low = mid+1;
            } else {
                high = mid-1;
            }

        }

        cout << res << endl;


    }

}

Compilation message (stderr)

index.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("O3")
      | 
index.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      |

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