Submission #5197060


Source Code Expand

Copy
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
#ifdef _MSC_VER
inline unsigned int __builtin_clz(unsigned int x){unsigned long r;_BitScanReverse(&r,x);return 31-r;}
#endif // _MSC_VER
template<class V> struct SparseTable { // [L,R)
    const V def = 0;
    inline V comp(V a, V b) { return a | b; }

    int n; vector<V> a, b[20]; inline int __lg(int x) { return 32 - 1 - __builtin_clz(x); }
    void init(vector<V> v) {
        int nn = v.size(); n = 1; while (n < nn) n *= 2; a.resize(n);
        rep(i, 0, 20) b[i].resize(n); rep(i, 0, nn) a[i] = v[i];

        int d = 1 << __lg(n - 1), e = d << 1;
        for (int h = 0, f; (f = 1 << h) <= d; ++h) {
            for (int i = f, r = f << 1; i < e; i += r) {
                b[h][i - 1] = a[i - 1];
                for (int j = i - 2; j >= i - f; --j) b[h][j] = comp(b[h][j + 1], a[j]);
                b[h][i] = a[i];
                for (int j = i + 1; j < i + f; ++j) b[h][j] = comp(b[h][j - 1], a[j]);
            }
        }
    }

    V get(int L,int R){assert(0<=L&&L<=R);if(L==R)return def;R--;if(L==R)return a[L];int h=__lg(L^R);
        return comp(b[h][L],b[h][R]);}};
/*---------------------------------------------------------------------------------------------------
            ∧_∧
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i
    /   \     | |
    /   / ̄ ̄ ̄ ̄/  |
  __(__ニつ/     _/ .| .|____
     \/____/ (u ⊃
---------------------------------------------------------------------------------------------------*/







ll N, K, A[101010];
SparseTable<ll> st;
//---------------------------------------------------------------------------------------------------
bool check(ll x) {
	ll cnt = 0;
	rep(i, 0, N) {
		if (x <= A[i]) {
			cnt += N - i;
			continue;
		}

		int ng = i, ok = N;
		while (ng + 1 != ok) {
			int md = (ng + ok) / 2;
			if (x <= st.get(i, md + 1)) ok = md;
			else ng = md;
		}
		cnt += N - ok;
	}

	return K <= cnt;
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> K;
	rep(i, 0, N) cin >> A[i];

	vector<ll> v;
	rep(i, 0, N) v.push_back(A[i]);
	st.init(v);

	ll ok = 0, ng = infl;
	while (ok + 1 != ng) {
		ll md = (ng + ok) / 2;
		if (check(md)) ok = md;
		else ng = md;
	}
	cout << ok << endl;
}

Submission Info

Submission Time
Task L - をあ ぷろぶれむ
User hamayanhamayan
Language C++14 (GCC 5.4.1)
Score 700
Code Size 3176 Byte
Status AC
Exec Time 386 ms
Memory 24308 KB

Judge Result

Set Name Sample Subtask1
Score / Max Score 0 / 0 700 / 700
Status
AC × 4
AC × 49
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
Subtask1 sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sub1_01.txt, sub1_02.txt, sub1_03.txt, sub1_04.txt, sub1_05.txt, sub1_06.txt, sub1_07.txt, sub1_08.txt, sub1_09.txt, sub1_10.txt, sub1_11.txt, sub1_12.txt, sub1_13.txt, sub1_14.txt, sub1_15.txt, sub1_16.txt, sub1_17.txt, sub1_18.txt, sub1_19.txt, sub1_20.txt, sub1_21.txt, sub1_22.txt, sub1_23.txt, sub1_24.txt, sub1_25.txt, sub2_01.txt, sub2_02.txt, sub2_03.txt, sub2_04.txt, sub2_05.txt, sub2_06.txt, sub2_07.txt, sub2_08.txt, sub2_09.txt, sub2_10.txt, sub2_11.txt, sub2_12.txt, sub2_13.txt, sub2_14.txt, sub2_15.txt, sub2_16.txt, sub2_17.txt, sub2_18.txt, sub2_19.txt, sub2_20.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
sample_04.txt AC 1 ms 256 KB
sub1_01.txt AC 3 ms 512 KB
sub1_02.txt AC 1 ms 256 KB
sub1_03.txt AC 1 ms 256 KB
sub1_04.txt AC 1 ms 256 KB
sub1_05.txt AC 3 ms 512 KB
sub1_06.txt AC 4 ms 512 KB
sub1_07.txt AC 1 ms 256 KB
sub1_08.txt AC 1 ms 256 KB
sub1_09.txt AC 2 ms 512 KB
sub1_10.txt AC 1 ms 256 KB
sub1_11.txt AC 4 ms 512 KB
sub1_12.txt AC 2 ms 512 KB
sub1_13.txt AC 3 ms 512 KB
sub1_14.txt AC 4 ms 512 KB
sub1_15.txt AC 1 ms 256 KB
sub1_16.txt AC 1 ms 256 KB
sub1_17.txt AC 3 ms 512 KB
sub1_18.txt AC 3 ms 512 KB
sub1_19.txt AC 2 ms 512 KB
sub1_20.txt AC 1 ms 256 KB
sub1_21.txt AC 1 ms 512 KB
sub1_22.txt AC 2 ms 512 KB
sub1_23.txt AC 2 ms 512 KB
sub1_24.txt AC 2 ms 512 KB
sub1_25.txt AC 3 ms 512 KB
sub2_01.txt AC 385 ms 24308 KB
sub2_02.txt AC 326 ms 24052 KB
sub2_03.txt AC 56 ms 24052 KB
sub2_04.txt AC 193 ms 12536 KB
sub2_05.txt AC 91 ms 24308 KB
sub2_06.txt AC 26 ms 12408 KB
sub2_07.txt AC 72 ms 24308 KB
sub2_08.txt AC 386 ms 24308 KB
sub2_09.txt AC 62 ms 24308 KB
sub2_10.txt AC 159 ms 12664 KB
sub2_11.txt AC 284 ms 24308 KB
sub2_12.txt AC 383 ms 24308 KB
sub2_13.txt AC 385 ms 24308 KB
sub2_14.txt AC 50 ms 12792 KB
sub2_15.txt AC 23 ms 12664 KB
sub2_16.txt AC 65 ms 24308 KB
sub2_17.txt AC 229 ms 12536 KB
sub2_18.txt AC 37 ms 24308 KB
sub2_19.txt AC 316 ms 23540 KB
sub2_20.txt AC 72 ms 24052 KB