oj.uz

Submission #476487

# Submission time Handle Problem Language Result Execution time Memory
476487 2021-09-27T10:30:38 Z neki Index (COCI21_index) C++14
60 / 110
 2500 ms 99476 KB 
#include <bits/stdc++.h>
#define ll int
#define loop(i, a, b) for(ll i=a;i<b;++i)
#define pool(i, a, b) for(ll i=a-1;i>=b;--i)
#define fore(i, a) for(auto&& i:a)
#define fi first
#define se second
#define ps(a) push_back(a)
#define pb(a) pop_back(a)
#define eb(...) emplace_back(__VA_ARGS__)
#define sc scanf
#define vc vector
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define llmax LLONG_MAX/2
#define llmin -LLONG_MAX/2
using namespace std;
#define mn 500100
#define par pair<ll, ll>
#define ld long double
#define mod 1000000007

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n, q;cin >> n >> q;
    
    vc<vc<ll>> tr(2 * n);
    loop(i, 0, n) {ll t;cin >> t;tr[i+n].eb(t);}
    pool(i, n, 1) tr[i].resize(tr[i * 2].size() + tr[i * 2 + 1].size());
    pool(no, n, 1) merge(all(tr[no * 2]), all(tr[no * 2 +1]), tr[no].begin());
    
    vc<vc<ll>> prno(q);
    
    loop(i, 0, q){
        ll ql, qr;cin >> ql >> qr;--ql;
        for(ql+=n, qr+=n;ql<qr;ql>>=1, qr>>=1){
            if(ql&1) prno[i].ps(ql++);
            if(qr&1) prno[i].ps(--qr);
        }
    }
    
    vc<ll> l(q, 1), r(q, n), mid(q);
    while(1){
        vc<ll> act;
        loop(i, 0, q) if(l[i]<r[i]) act.ps(i), mid[i]=(l[i]+r[i]+1)/2;
        if(act.size()==0) break;
        //sort(all(act), [&](ll a, ll b){return mid[a]<mid[b];});
        
        vc<vc<ll>> ques(2 * n);
        vc<ll> sum(q, 0);
        fore(i, act){
            fore(v, prno[i]) ques[v].eb(i);
        }
        
        loop(i, 1, 2 * n) fore(v, ques[i]){
            sum[v]+=tr[i].end()-lower_bound(all(tr[i]), mid[v]);
        }
        
        fore(i, act){
            if(mid[i]<=sum[i]) l[i]=mid[i];
            else r[i]=mid[i]-1;
        }
    }
    loop(i, 0, q) cout << l[i] << endl;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 588 KB Output is correct
2 Correct 7 ms 588 KB Output is correct
3 Correct 6 ms 588 KB Output is correct
4 Correct 7 ms 588 KB Output is correct
5 Correct 5 ms 588 KB Output is correct
6 Correct 5 ms 588 KB Output is correct
7 Correct 6 ms 588 KB Output is correct
8 Correct 6 ms 588 KB Output is correct
9 Correct 6 ms 588 KB Output is correct
10 Correct 6 ms 588 KB Output is correct
11 Correct 602 ms 23552 KB Output is correct
12 Correct 607 ms 23620 KB Output is correct
13 Correct 600 ms 23644 KB Output is correct
14 Correct 608 ms 23232 KB Output is correct
15 Correct 610 ms 23996 KB Output is correct
16 Correct 626 ms 23616 KB Output is correct
17 Correct 612 ms 23216 KB Output is correct
18 Correct 596 ms 23476 KB Output is correct
19 Correct 603 ms 23532 KB Output is correct
20 Correct 606 ms 23548 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 588 KB Output is correct
2 Correct 7 ms 588 KB Output is correct
3 Correct 6 ms 588 KB Output is correct
4 Correct 7 ms 588 KB Output is correct
5 Correct 5 ms 588 KB Output is correct
6 Correct 5 ms 588 KB Output is correct
7 Correct 6 ms 588 KB Output is correct
8 Correct 6 ms 588 KB Output is correct
9 Correct 6 ms 588 KB Output is correct
10 Correct 6 ms 588 KB Output is correct
11 Correct 602 ms 23552 KB Output is correct
12 Correct 607 ms 23620 KB Output is correct
13 Correct 600 ms 23644 KB Output is correct
14 Correct 608 ms 23232 KB Output is correct
15 Correct 610 ms 23996 KB Output is correct
16 Correct 626 ms 23616 KB Output is correct
17 Correct 612 ms 23216 KB Output is correct
18 Correct 596 ms 23476 KB Output is correct
19 Correct 603 ms 23532 KB Output is correct
20 Correct 606 ms 23548 KB Output is correct
21 Execution timed out 2583 ms 99476 KB Time limit exceeded
22 Halted 0 ms 0 KB -