oj.uz

Submission #1110735

# Submission time Handle Problem Language Result Execution time Memory
1110735 2024-11-10T09:43:08 Z luvna Index (COCI21_index) C++14
110 / 110
 425 ms 23252 KB 
#include<bits/stdc++.h>

#define all(v) v.begin(), v.end()
#define endl "\n"

using namespace std;

const int N = 2e5 + 15;

int n, q;
int a[N];
int L[N], R[N];
vector<int> candidate[N];
vector<int> evt;
int bit[N];
pair<int,int> qu[N];
int ans[N];

void update(int idx, int v){
    for(;idx <= n; idx += (idx & (-idx))) bit[idx] += v;
}

int get(int l, int r){int res = 0; l--;
    for(;r; r -= (r & (-r))) res += bit[r];
    for(;l; l -= (l & (-l))) res -= bit[l];
    return res;
}

void solve(){
    cin >> n >> q;

    for(int i = 1; i <= n; i++) cin >> a[i], evt.push_back(i);

    sort(all(evt), [&](int x, int y){
        return a[x] > a[y];
    });

    for(int i = 1; i <= q; i++){
        int l, r; cin >> l >> r;
        qu[i] = {l,r};
        L[i] = 1, R[i] = r - l + 1;
    }

    while(true){
        bool any = false;
        for(int i = 1; i <= q; i++){
            if(L[i] > R[i]) continue;
            int mid = (L[i] + R[i]) >> 1;
            candidate[mid].push_back(i);
            any = true;
        }
        if(!any) break;
        for(int mid = n, j = 0; mid >= 1; mid--){
            while(j < evt.size() && a[evt[j]] >= mid){
                update(evt[j],1);
                j++;
            }
            for(int i : candidate[mid]){
                if(get(qu[i].first,qu[i].second) >= mid){
                    ans[i] = mid;
                    L[i] = mid+1;
                }
                else R[i] = mid-1;
            }
            candidate[mid].clear();
        }
        for(int i = 1; i <= n; i++) bit[i] = 0;
    }

    for(int i = 1; i <= q; i++) cout << ans[i] << endl;
}

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

    #define task "task"

    if(fopen(task".INP", "r")){
        freopen(task".INP", "r", stdin);
        freopen(task".OUT", "w", stdout);
    }

    int t; t = 1; //cin >> t;
    while(t--) solve();
}

Compilation message

index.cpp: In function 'void solve()':
index.cpp:54:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             while(j < evt.size() && a[evt[j]] >= mid){
      |                   ~~^~~~~~~~~~~~
index.cpp: In function 'int main()':
index.cpp:80:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         freopen(task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
index.cpp:81:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         freopen(task".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8528 KB Output is correct
2 Correct 3 ms 8528 KB Output is correct
3 Correct 2 ms 8528 KB Output is correct
4 Correct 3 ms 8528 KB Output is correct
5 Correct 3 ms 8752 KB Output is correct
6 Correct 3 ms 8528 KB Output is correct
7 Correct 2 ms 8528 KB Output is correct
8 Correct 3 ms 8528 KB Output is correct
9 Correct 3 ms 8528 KB Output is correct
10 Correct 3 ms 8528 KB Output is correct
11 Correct 81 ms 12236 KB Output is correct
12 Correct 73 ms 12136 KB Output is correct
13 Correct 73 ms 12240 KB Output is correct
14 Correct 74 ms 12236 KB Output is correct
15 Correct 82 ms 12208 KB Output is correct
16 Correct 74 ms 12212 KB Output is correct
17 Correct 74 ms 12212 KB Output is correct
18 Correct 74 ms 12264 KB Output is correct
19 Correct 73 ms 12236 KB Output is correct
20 Correct 72 ms 12168 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8528 KB Output is correct
2 Correct 3 ms 8528 KB Output is correct
3 Correct 2 ms 8528 KB Output is correct
4 Correct 3 ms 8528 KB Output is correct
5 Correct 3 ms 8752 KB Output is correct
6 Correct 3 ms 8528 KB Output is correct
7 Correct 2 ms 8528 KB Output is correct
8 Correct 3 ms 8528 KB Output is correct
9 Correct 3 ms 8528 KB Output is correct
10 Correct 3 ms 8528 KB Output is correct
11 Correct 81 ms 12236 KB Output is correct
12 Correct 73 ms 12136 KB Output is correct
13 Correct 73 ms 12240 KB Output is correct
14 Correct 74 ms 12236 KB Output is correct
15 Correct 82 ms 12208 KB Output is correct
16 Correct 74 ms 12212 KB Output is correct
17 Correct 74 ms 12212 KB Output is correct
18 Correct 74 ms 12264 KB Output is correct
19 Correct 73 ms 12236 KB Output is correct
20 Correct 72 ms 12168 KB Output is correct
21 Correct 382 ms 22984 KB Output is correct
22 Correct 371 ms 22980 KB Output is correct
23 Correct 371 ms 22980 KB Output is correct
24 Correct 354 ms 22980 KB Output is correct
25 Correct 425 ms 23252 KB Output is correct
26 Correct 388 ms 22980 KB Output is correct
27 Correct 377 ms 23056 KB Output is correct
28 Correct 380 ms 22980 KB Output is correct
29 Correct 390 ms 23220 KB Output is correct
30 Correct 376 ms 23008 KB Output is correct