oj.uz

Submission #1108221

# Submission time Handle Problem Language Result Execution time Memory
1108221 2024-11-03T10:59:37 Z InvMOD Index (COCI21_index) C++14
110 / 110
 372 ms 33112 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define gcd __gcd
#define sz(v) (int) v.size()
#define pb push_back
#define pi pair<int,int>
#define all(v) (v).begin(), (v).end()
#define compact(v) (v).erase(unique(all(v)), (v).end())
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define dbg(x) "[" #x " = " << (x) << "]"
///#define int long long

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template<typename T> bool ckmx(T& a, const T& b){if(a < b) return a = b, true; return false;}
template<typename T> bool ckmn(T& a, const T& b){if(a > b) return a = b, true; return false;}

const int N = 2e5+5;
const ll MOD = 1e9+7;
const ll INF = 1e18;



int n, q, a[N], b[N];

int ql[N], qr[N], bit[N];

pair<int,int> Q[N];
vector<int> md[N];

void update(int p, int val){
    for(; p <= n; p += p&-p) bit[p] += val;
    return;
}

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

int get_range(int l, int r){
    return get(r) - get(l-1);
}

void solve()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        b[i] = i;
    }

    for(int i = 1; i <= q; i++){
        cin >> Q[i].first >> Q[i].second;
        ql[i] = 1, qr[i] = 2e5+1;
    }

    sort(b+1, b+1+n, [&](int x, int y){
            return a[x] > a[y];
    });

    bool changed = true;
    while(changed){

        changed = false;
        for(int i = 1; i <= q; i++){
            if(ql[i]+1 < qr[i]){
                changed = true;
                md[ql[i]+qr[i]>>1].push_back(i);
            }
        }

        for(int i = 2e5, j = 1; i >= 1; i--){
            while(a[b[j]] >= i) update(b[j], 1), j++;

            while(md[i].size()){
                int id = md[i].back();

                int l = Q[id].first, r = Q[id].second;
                if(get_range(l, r) >= i) ql[id] = i;
                else{
                    qr[id] = i;
                }

                md[i].pop_back();
            }
        }

        for(int i = 1; i <= n; i++) bit[i] = 0;
    }

    for(int i = 1; i <= q; i++) cout << ql[i] <<"\n";
}

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

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP","r",stdin);
        freopen(name".OUT","w",stdout);
    }

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

Compilation message

index.cpp: In function 'void solve()':
index.cpp:75:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |                 md[ql[i]+qr[i]>>1].push_back(i);
      |                    ~~~~~^~~~~~
index.cpp: In function 'int main()':
index.cpp:109:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         freopen(name".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
index.cpp:110:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         freopen(name".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8784 KB Output is correct
2 Correct 8 ms 8784 KB Output is correct
3 Correct 8 ms 8784 KB Output is correct
4 Correct 10 ms 8784 KB Output is correct
5 Correct 8 ms 8784 KB Output is correct
6 Correct 8 ms 8928 KB Output is correct
7 Correct 11 ms 8784 KB Output is correct
8 Correct 8 ms 8784 KB Output is correct
9 Correct 8 ms 8928 KB Output is correct
10 Correct 10 ms 8784 KB Output is correct
11 Correct 74 ms 14404 KB Output is correct
12 Correct 77 ms 14504 KB Output is correct
13 Correct 75 ms 14552 KB Output is correct
14 Correct 73 ms 14556 KB Output is correct
15 Correct 80 ms 14556 KB Output is correct
16 Correct 84 ms 14556 KB Output is correct
17 Correct 75 ms 14572 KB Output is correct
18 Correct 74 ms 14564 KB Output is correct
19 Correct 73 ms 14656 KB Output is correct
20 Correct 77 ms 14580 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8784 KB Output is correct
2 Correct 8 ms 8784 KB Output is correct
3 Correct 8 ms 8784 KB Output is correct
4 Correct 10 ms 8784 KB Output is correct
5 Correct 8 ms 8784 KB Output is correct
6 Correct 8 ms 8928 KB Output is correct
7 Correct 11 ms 8784 KB Output is correct
8 Correct 8 ms 8784 KB Output is correct
9 Correct 8 ms 8928 KB Output is correct
10 Correct 10 ms 8784 KB Output is correct
11 Correct 74 ms 14404 KB Output is correct
12 Correct 77 ms 14504 KB Output is correct
13 Correct 75 ms 14552 KB Output is correct
14 Correct 73 ms 14556 KB Output is correct
15 Correct 80 ms 14556 KB Output is correct
16 Correct 84 ms 14556 KB Output is correct
17 Correct 75 ms 14572 KB Output is correct
18 Correct 74 ms 14564 KB Output is correct
19 Correct 73 ms 14656 KB Output is correct
20 Correct 77 ms 14580 KB Output is correct
21 Correct 343 ms 32932 KB Output is correct
22 Correct 357 ms 32724 KB Output is correct
23 Correct 372 ms 32928 KB Output is correct
24 Correct 343 ms 32980 KB Output is correct
25 Correct 363 ms 33112 KB Output is correct
26 Correct 342 ms 32724 KB Output is correct
27 Correct 369 ms 32716 KB Output is correct
28 Correct 340 ms 32980 KB Output is correct
29 Correct 351 ms 32796 KB Output is correct
30 Correct 326 ms 32468 KB Output is correct