oj.uz

Submission #943259

# Submission time Handle Problem Language Result Execution time Memory
943259 2024-03-11T09:44:18 Z WeIlIaN Index (COCI21_index) C++17
60 / 110
 2500 ms 42724 KB 
#include <bits/stdc++.h>
using namespace std;

#define MOD 1000000007
#define fir first
#define sec second
#define pushf push_front
#define pushb push_back
#define popf pop_front
#define popb pop_back
#define mp make_pair
#define all(a) a.begin(), a.end()

#define FOR(i, s, e) for(int i = s; i < e; i++)
#define RFOR(i, s, e) for(int i = e-1; i >= s; i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, 0, n)

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vb> vvb;
typedef vector<vc> vvc;
typedef vector<vs> vvs;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
typedef queue<int> qi;
typedef queue<ll> qll;
typedef queue<pii> qpii;
typedef queue<pll> qpll;
typedef deque<int> dqi;
typedef deque<ll> dqll;
typedef deque<pii> dqpii;
typedef deque<pll> dqpll;
typedef priority_queue<int> pqi;
typedef priority_queue<ll> pqll;
typedef priority_queue<pii> pqpii;
typedef priority_queue<pll> pqpll;
typedef priority_queue<int, vi, greater<int> > r_pqi;
typedef priority_queue<ll, vll, greater<ll> > r_pqll;
typedef priority_queue<pii, vpii, greater<pii> > r_pqpii;
typedef priority_queue<pll, vpll, greater<pll> > r_pqpll;

vvi seg;
int n, q, t;

int cnt(int a, int b, int val, int cur, int l, int r) {
    if(b < l || a > r) {
        return 0;
    }
    if(a <= l && b >= r) {
        return seg[cur].size() - (lower_bound(all(seg[cur]), val)-seg[cur].begin());
    }
    int m = (l + r) / 2;
    return cnt(a, b, val, 2 * cur, l, m) + cnt(a, b, val, 2 * cur + 1, m + 1, r);
}



signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    t = 1;
    while(t < n) {
        t *= 2;
    }
    seg.resize(2 * t);
    vi arr(n);
    int x;
    REP(i, n) {
        cin>>arr[i];
        seg[i+t] = {arr[i]};
    }
    sort(all(arr));
    RFOR(i, 1, t) {
        seg[i].resize(seg[i*2].size() + seg[i*2+1].size());
        merge(all(seg[i*2]), all(seg[i*2+1]), seg[i].begin());
    }
    int a, b, left, right, mid;
    REP(i, q) {
        cin>>a>>b;
        left = 0, right = 200001;
        while(right - left > 1) {
            mid = (left + right) / 2;
            if(cnt(a, b, mid, 1, 1, t) >= mid) {
                left = mid;
            }
            else {
                right = mid;
            }
        }
        cout<<left<<endl;
    }
}

Compilation message

index.cpp: In function 'int main()':
index.cpp:80:9: warning: unused variable 'x' [-Wunused-variable]
   80 |     int x;
      |         ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 604 KB Output is correct
2 Correct 5 ms 604 KB Output is correct
3 Correct 5 ms 604 KB Output is correct
4 Correct 5 ms 460 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 5 ms 604 KB Output is correct
7 Correct 5 ms 604 KB Output is correct
8 Correct 6 ms 756 KB Output is correct
9 Correct 5 ms 604 KB Output is correct
10 Correct 5 ms 604 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 604 KB Output is correct
2 Correct 5 ms 604 KB Output is correct
3 Correct 5 ms 604 KB Output is correct
4 Correct 5 ms 460 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 5 ms 604 KB Output is correct
7 Correct 5 ms 604 KB Output is correct
8 Correct 6 ms 756 KB Output is correct
9 Correct 5 ms 604 KB Output is correct
10 Correct 5 ms 604 KB Output is correct
11 Correct 557 ms 10420 KB Output is correct
12 Correct 548 ms 10504 KB Output is correct
13 Correct 556 ms 10396 KB Output is correct
14 Correct 550 ms 10496 KB Output is correct
15 Correct 557 ms 10464 KB Output is correct
16 Correct 553 ms 10356 KB Output is correct
17 Correct 560 ms 10960 KB Output is correct
18 Correct 547 ms 10488 KB Output is correct
19 Correct 574 ms 10544 KB Output is correct
20 Correct 562 ms 10836 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 604 KB Output is correct
2 Correct 5 ms 604 KB Output is correct
3 Correct 5 ms 604 KB Output is correct
4 Correct 5 ms 460 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 5 ms 604 KB Output is correct
7 Correct 5 ms 604 KB Output is correct
8 Correct 6 ms 756 KB Output is correct
9 Correct 5 ms 604 KB Output is correct
10 Correct 5 ms 604 KB Output is correct
11 Correct 557 ms 10420 KB Output is correct
12 Correct 548 ms 10504 KB Output is correct
13 Correct 556 ms 10396 KB Output is correct
14 Correct 550 ms 10496 KB Output is correct
15 Correct 557 ms 10464 KB Output is correct
16 Correct 553 ms 10356 KB Output is correct
17 Correct 560 ms 10960 KB Output is correct
18 Correct 547 ms 10488 KB Output is correct
19 Correct 574 ms 10544 KB Output is correct
20 Correct 562 ms 10836 KB Output is correct
21 Execution timed out 2598 ms 42724 KB Time limit exceeded
22 Halted 0 ms 0 KB -