oj.uz

답안 #954090

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
954090 2024-03-27T09:11:15 Z Beerus13 Index (COCI21_index) C++14
110 / 110
 239 ms 37536 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
 
int n, q, a[N], ans[N];
int bit[N];
 
struct query {
    int l, r, id;
}; 
 
vector<int> pos[N];
vector<query> queries;
 
void update(int i, int val) {
    for(; i < N; i += i & -i) bit[i] += val;
}
 
int get(int i) {
    int res = 0;
    for(; i; i -= i & -i) res += bit[i];
    return res;
}
 
int Sum(int l, int r) {
    return get(r) - get(l - 1);
}
 
void solve(int l, int r, vector<query> &queries) {
    if(queries.empty()) return;
    if(l == r) {
        for(auto it : queries) ans[it.id] = l;
        return;
    }
    vector<query> L, R;
    int mid = l + r >> 1;
    for(int i = mid + 1; i <= r; ++i) {
        for(int j : pos[i]) update(j, 1);
    }
    for(auto it : queries) {
        if(Sum(it.l, it.r) > mid) R.push_back(it);
        else L.push_back(it);
    }
    solve(l, mid, L);
    for(int i = mid + 1; i <= r; ++i) {
        for(int j : pos[i]) update(j, -1);
    }
    solve(mid + 1, r, R);
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        pos[a[i]].push_back(i);
    }
    for(int i = 1; i <= q; ++i) {
        int l, r; cin >> l >> r;
        queries.push_back({l, r, i});
    }
    solve(1, (int)2e5, queries);
    for(int i = 1; i <= q; ++i) cout << ans[i] << '\n';
    return 0;
}
 
// https://oj.vnoi.info/problem/coci2021_r6_index

Compilation message

index.cpp: In function 'void solve(int, int, std::vector<query>&)':
index.cpp:36:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 7000 KB Output is correct
2 Correct 3 ms 7000 KB Output is correct
3 Correct 4 ms 7004 KB Output is correct
4 Correct 2 ms 6804 KB Output is correct
5 Correct 3 ms 7004 KB Output is correct
6 Correct 3 ms 7004 KB Output is correct
7 Correct 3 ms 7004 KB Output is correct
8 Correct 3 ms 7004 KB Output is correct
9 Correct 3 ms 6808 KB Output is correct
10 Correct 3 ms 7000 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 7000 KB Output is correct
2 Correct 3 ms 7000 KB Output is correct
3 Correct 4 ms 7004 KB Output is correct
4 Correct 2 ms 6804 KB Output is correct
5 Correct 3 ms 7004 KB Output is correct
6 Correct 3 ms 7004 KB Output is correct
7 Correct 3 ms 7004 KB Output is correct
8 Correct 3 ms 7004 KB Output is correct
9 Correct 3 ms 6808 KB Output is correct
10 Correct 3 ms 7000 KB Output is correct
11 Correct 54 ms 14848 KB Output is correct
12 Correct 50 ms 14676 KB Output is correct
13 Correct 53 ms 14616 KB Output is correct
14 Correct 50 ms 14640 KB Output is correct
15 Correct 50 ms 14640 KB Output is correct
16 Correct 60 ms 14744 KB Output is correct
17 Correct 51 ms 14776 KB Output is correct
18 Correct 52 ms 14792 KB Output is correct
19 Correct 50 ms 14568 KB Output is correct
20 Correct 50 ms 14556 KB Output is correct

Subtask #3
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 7000 KB Output is correct
2 Correct 3 ms 7000 KB Output is correct
3 Correct 4 ms 7004 KB Output is correct
4 Correct 2 ms 6804 KB Output is correct
5 Correct 3 ms 7004 KB Output is correct
6 Correct 3 ms 7004 KB Output is correct
7 Correct 3 ms 7004 KB Output is correct
8 Correct 3 ms 7004 KB Output is correct
9 Correct 3 ms 6808 KB Output is correct
10 Correct 3 ms 7000 KB Output is correct
11 Correct 54 ms 14848 KB Output is correct
12 Correct 50 ms 14676 KB Output is correct
13 Correct 53 ms 14616 KB Output is correct
14 Correct 50 ms 14640 KB Output is correct
15 Correct 50 ms 14640 KB Output is correct
16 Correct 60 ms 14744 KB Output is correct
17 Correct 51 ms 14776 KB Output is correct
18 Correct 52 ms 14792 KB Output is correct
19 Correct 50 ms 14568 KB Output is correct
20 Correct 50 ms 14556 KB Output is correct
21 Correct 219 ms 35524 KB Output is correct
22 Correct 210 ms 35532 KB Output is correct
23 Correct 208 ms 35664 KB Output is correct
24 Correct 210 ms 34508 KB Output is correct
25 Correct 239 ms 37208 KB Output is correct
26 Correct 214 ms 35136 KB Output is correct
27 Correct 236 ms 35924 KB Output is correct
28 Correct 209 ms 36272 KB Output is correct
29 Correct 217 ms 35628 KB Output is correct
30 Correct 226 ms 37536 KB Output is correct