oj.uz

답안 #671982

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
671982 2022-12-14T13:59:17 Z mychecksedad Index (COCI21_index) C++17
60 / 110
 1621 ms 137828 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 = 3e5+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];
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

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 36180 KB Output is correct
2 Correct 28 ms 36180 KB Output is correct
3 Correct 27 ms 36180 KB Output is correct
4 Correct 27 ms 36256 KB Output is correct
5 Correct 29 ms 36180 KB Output is correct
6 Correct 28 ms 36208 KB Output is correct
7 Correct 31 ms 36180 KB Output is correct
8 Correct 27 ms 36200 KB Output is correct
9 Correct 28 ms 36260 KB Output is correct
10 Correct 29 ms 36224 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 36180 KB Output is correct
2 Correct 28 ms 36180 KB Output is correct
3 Correct 27 ms 36180 KB Output is correct
4 Correct 27 ms 36256 KB Output is correct
5 Correct 29 ms 36180 KB Output is correct
6 Correct 28 ms 36208 KB Output is correct
7 Correct 31 ms 36180 KB Output is correct
8 Correct 27 ms 36200 KB Output is correct
9 Correct 28 ms 36260 KB Output is correct
10 Correct 29 ms 36224 KB Output is correct
11 Correct 1621 ms 64456 KB Output is correct
12 Correct 1572 ms 64496 KB Output is correct
13 Correct 1535 ms 65088 KB Output is correct
14 Correct 1602 ms 64272 KB Output is correct
15 Correct 1579 ms 64336 KB Output is correct
16 Correct 1595 ms 64472 KB Output is correct
17 Correct 1588 ms 64384 KB Output is correct
18 Correct 1587 ms 64372 KB Output is correct
19 Correct 1558 ms 64660 KB Output is correct
20 Correct 1571 ms 64508 KB Output is correct

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 36180 KB Output is correct
2 Correct 28 ms 36180 KB Output is correct
3 Correct 27 ms 36180 KB Output is correct
4 Correct 27 ms 36256 KB Output is correct
5 Correct 29 ms 36180 KB Output is correct
6 Correct 28 ms 36208 KB Output is correct
7 Correct 31 ms 36180 KB Output is correct
8 Correct 27 ms 36200 KB Output is correct
9 Correct 28 ms 36260 KB Output is correct
10 Correct 29 ms 36224 KB Output is correct
11 Correct 1621 ms 64456 KB Output is correct
12 Correct 1572 ms 64496 KB Output is correct
13 Correct 1535 ms 65088 KB Output is correct
14 Correct 1602 ms 64272 KB Output is correct
15 Correct 1579 ms 64336 KB Output is correct
16 Correct 1595 ms 64472 KB Output is correct
17 Correct 1588 ms 64384 KB Output is correct
18 Correct 1587 ms 64372 KB Output is correct
19 Correct 1558 ms 64660 KB Output is correct
20 Correct 1571 ms 64508 KB Output is correct
21 Runtime error 178 ms 137828 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -