oj.uz

Submission #671980

# Submission time Handle Problem Language Result Execution time Memory
671980 2022-12-14T13:56:50 Z mychecksedad Index (COCI21_index) C++17
60 / 110
 1661 ms 117552 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+100, 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];
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]));  
    // cout << l << ' ' << r << ": ";
    // for(int u: t[k]) cout << u << ' ';
    // cout << '\n';
}

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;
    while(ok){
        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;
                }
            }
        }
        cout << '\n';
    }

    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:120:16: warning: unused variable 'aa' [-Wunused-variable]
  120 |     int T = 1, aa;
      |                ^~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 24472 KB Output is correct
2 Correct 22 ms 24440 KB Output is correct
3 Correct 22 ms 24428 KB Output is correct
4 Correct 22 ms 24456 KB Output is correct
5 Correct 23 ms 24476 KB Output is correct
6 Correct 24 ms 24496 KB Output is correct
7 Correct 22 ms 24404 KB Output is correct
8 Correct 23 ms 24456 KB Output is correct
9 Correct 22 ms 24476 KB Output is correct
10 Correct 23 ms 24452 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 24472 KB Output is correct
2 Correct 22 ms 24440 KB Output is correct
3 Correct 22 ms 24428 KB Output is correct
4 Correct 22 ms 24456 KB Output is correct
5 Correct 23 ms 24476 KB Output is correct
6 Correct 24 ms 24496 KB Output is correct
7 Correct 22 ms 24404 KB Output is correct
8 Correct 23 ms 24456 KB Output is correct
9 Correct 22 ms 24476 KB Output is correct
10 Correct 23 ms 24452 KB Output is correct
11 Correct 1614 ms 53712 KB Output is correct
12 Correct 1591 ms 53324 KB Output is correct
13 Correct 1538 ms 54212 KB Output is correct
14 Correct 1636 ms 53628 KB Output is correct
15 Correct 1598 ms 53304 KB Output is correct
16 Correct 1661 ms 53456 KB Output is correct
17 Correct 1622 ms 53436 KB Output is correct
18 Correct 1586 ms 53492 KB Output is correct
19 Correct 1611 ms 53760 KB Output is correct
20 Correct 1570 ms 53436 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 24472 KB Output is correct
2 Correct 22 ms 24440 KB Output is correct
3 Correct 22 ms 24428 KB Output is correct
4 Correct 22 ms 24456 KB Output is correct
5 Correct 23 ms 24476 KB Output is correct
6 Correct 24 ms 24496 KB Output is correct
7 Correct 22 ms 24404 KB Output is correct
8 Correct 23 ms 24456 KB Output is correct
9 Correct 22 ms 24476 KB Output is correct
10 Correct 23 ms 24452 KB Output is correct
11 Correct 1614 ms 53712 KB Output is correct
12 Correct 1591 ms 53324 KB Output is correct
13 Correct 1538 ms 54212 KB Output is correct
14 Correct 1636 ms 53628 KB Output is correct
15 Correct 1598 ms 53304 KB Output is correct
16 Correct 1661 ms 53456 KB Output is correct
17 Correct 1622 ms 53436 KB Output is correct
18 Correct 1586 ms 53492 KB Output is correct
19 Correct 1611 ms 53760 KB Output is correct
20 Correct 1570 ms 53436 KB Output is correct
21 Runtime error 168 ms 117552 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -