oj.uz

Submission #671984

# Submission time Handle Problem Language Result Execution time Memory
671984 2022-12-14T14:02:10 Z mychecksedad Index (COCI21_index) C++17
60 / 110
 2500 ms 154232 KB 
/* Author : Mychecksdead */
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD1 (1000000000+7)
#define MOD (998244353)
#define PI 3.1415926535
#define pb push_back
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " is " << x << '\n';
const int N = 2e5+500, M = 1e5+10, F = 2147483646, K = 20;


int n, q, a[N], res[N];
vector<array<int, 5>> Q;
vector<array<int, 3>> searchs[N*4];
vector<int> t[N*4];

void build(int l, int r, int k){
    if(l == r){
        t[k] = {0, a[l]};
        return;
    }
    int m = (l+r)>>1;
    build(l, m, k<<1);
    build(m+1, r, k<<1|1);
    merge(t[k<<1].begin() + 1, t[k<<1].end(), all(t[k<<1|1]), back_inserter(t[k]));  
}

void add_bs(int l, int r, int ql, int qr, int k, int val, int idx){
    if(ql > r || l > qr) return;
    if(ql <= l && r <= qr){
        searchs[k].pb({val, idx, int(t[k].size())});
        return;
    }
    int m = (l + r) >> 1;
    add_bs(l, m, ql, qr, k<<1, val, idx);
    add_bs(m+1, r, ql, qr, k<<1|1, val, idx);
}

void s(int k, int l, int r, vector<array<int, 3>> v){
    if(v.empty() || r < l) return;
    int m = (l + r) >> 1;
    vector<array<int, 3>> s_l, s_r;
    for(auto u: v){
        int val = u[0], idx = u[1];
        if(val <= t[k][m]){
            res[idx] -= t[k].size() - u[2];
            res[idx] += t[k].size() - m;
            u[2] = m;
            // cout << u[0] << ' ' << u[1] << ':' << m << '\n';
            s_l.pb(u);
        }else{
            s_r.pb(u);
        }
    }
    s(k, l, m - 1, s_l);
    s(k, m + 1, r, s_r);
}

void proc(){
    for(int k = 1; k <= 4*n; ++k){
        if(searchs[k].empty()) continue;
        s(k, 0, t[k].size() - 1, searchs[k]);
        searchs[k].clear();
    }
}

void solve(){
    cin >> n >> q;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 0; i < q; ++i){
        int l, r; cin >> l >> r;
        Q.pb({l, r, 1, r - l + 1, 0});
    }
    build(1, n, 1);
    bool ok = 1;
    int x = 0;
    while(ok && x < 40){
        x++;
        ok = 0;
        for(int i = 0; i < q; ++i){
            if(Q[i][2] <= Q[i][3]){
                res[i] = 0;
                int m = (Q[i][2] + Q[i][3]) >> 1;
                add_bs(1, n, Q[i][0], Q[i][1], 1, m, i);
                ok = 1;
            }
        }
        if(!ok) break;
        proc();
        for(int i = 0; i < q; ++i){
            if(Q[i][2] <= Q[i][3]){
                // cout << res[i] << ' ' << Q[i][2] << ' ' << Q[i][3] << '\n';
                int m = (Q[i][2] + Q[i][3]) >> 1;
                if(res[i] >= m){
                    Q[i][4] = m;
                    Q[i][2] = m + 1;
                }else{
                    Q[i][3] = m - 1;
                }
            }
        }
    }

    for(int i = 0; i < q; ++i) cout << Q[i][4] << '\n';
}




int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int T = 1, aa;
    // cin >> T;aa=T;
    while(T--){
        // cout << "Case #" << aa-T << ": ";
        solve();
        cout << '\n';
    }
    return 0;
 
}

Compilation message

index.cpp: In function 'int main()':
index.cpp:118:16: warning: unused variable 'aa' [-Wunused-variable]
  118 |     int T = 1, aa;
      |                ^~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 38612 KB Output is correct
2 Correct 28 ms 38540 KB Output is correct
3 Correct 27 ms 38536 KB Output is correct
4 Correct 29 ms 38612 KB Output is correct
5 Correct 28 ms 38612 KB Output is correct
6 Correct 28 ms 38584 KB Output is correct
7 Correct 27 ms 38580 KB Output is correct
8 Correct 28 ms 38572 KB Output is correct
9 Correct 28 ms 38636 KB Output is correct
10 Correct 36 ms 38588 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 38612 KB Output is correct
2 Correct 28 ms 38540 KB Output is correct
3 Correct 27 ms 38536 KB Output is correct
4 Correct 29 ms 38612 KB Output is correct
5 Correct 28 ms 38612 KB Output is correct
6 Correct 28 ms 38584 KB Output is correct
7 Correct 27 ms 38580 KB Output is correct
8 Correct 28 ms 38572 KB Output is correct
9 Correct 28 ms 38636 KB Output is correct
10 Correct 36 ms 38588 KB Output is correct
11 Correct 1607 ms 66896 KB Output is correct
12 Correct 1676 ms 66720 KB Output is correct
13 Correct 1605 ms 67472 KB Output is correct
14 Correct 1736 ms 66660 KB Output is correct
15 Correct 1653 ms 66576 KB Output is correct
16 Correct 1598 ms 66884 KB Output is correct
17 Correct 1601 ms 66620 KB Output is correct
18 Correct 1589 ms 67064 KB Output is correct
19 Correct 1608 ms 67096 KB Output is correct
20 Correct 1555 ms 66804 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 38612 KB Output is correct
2 Correct 28 ms 38540 KB Output is correct
3 Correct 27 ms 38536 KB Output is correct
4 Correct 29 ms 38612 KB Output is correct
5 Correct 28 ms 38612 KB Output is correct
6 Correct 28 ms 38584 KB Output is correct
7 Correct 27 ms 38580 KB Output is correct
8 Correct 28 ms 38572 KB Output is correct
9 Correct 28 ms 38636 KB Output is correct
10 Correct 36 ms 38588 KB Output is correct
11 Correct 1607 ms 66896 KB Output is correct
12 Correct 1676 ms 66720 KB Output is correct
13 Correct 1605 ms 67472 KB Output is correct
14 Correct 1736 ms 66660 KB Output is correct
15 Correct 1653 ms 66576 KB Output is correct
16 Correct 1598 ms 66884 KB Output is correct
17 Correct 1601 ms 66620 KB Output is correct
18 Correct 1589 ms 67064 KB Output is correct
19 Correct 1608 ms 67096 KB Output is correct
20 Correct 1555 ms 66804 KB Output is correct
21 Execution timed out 2603 ms 154232 KB Time limit exceeded
22 Halted 0 ms 0 KB -