oj.uz

Submission #476483

# Submission time Handle Problem Language Result Execution time Memory
476483 2021-09-27T10:18:37 Z neki Index (COCI21_index) C++14
60 / 110
 2500 ms 98992 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);
    vc<ll> l(q, 1), r(q), mid(q);
    loop(i, 0, q){
        ll ql, qr;cin >> ql >> qr;--ql;
        r[i]=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);
        }
    }
    
    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) if(ques[i].size()){
            loop(j, 0, tr[i].size()) while(ques[i].size() and tr[i][j]>=mid[ques[i].back()]){
                sum[ques[i].back()]+=tr[i].size()-j;
                ques[i].pop_back();
            } 
        }
        
        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;
}

Compilation message

index.cpp: In function 'int main()':
index.cpp:3:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define loop(i, a, b) for(ll i=a;i<b;++i)
......
   58 |             loop(j, 0, tr[i].size()) while(ques[i].size() and tr[i][j]>=mid[ques[i].back()]){
      |                  ~~~~~~~~~~~~~~~~~~
index.cpp:58:13: note: in expansion of macro 'loop'
   58 |             loop(j, 0, tr[i].size()) while(ques[i].size() and tr[i][j]>=mid[ques[i].back()]){
      |             ^~~~

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 7 ms 588 KB Output is correct
4 Correct 7 ms 588 KB Output is correct
5 Correct 11 ms 588 KB Output is correct
6 Correct 6 ms 588 KB Output is correct
7 Correct 6 ms 588 KB Output is correct
8 Correct 6 ms 692 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 7 ms 588 KB Output is correct
4 Correct 7 ms 588 KB Output is correct
5 Correct 11 ms 588 KB Output is correct
6 Correct 6 ms 588 KB Output is correct
7 Correct 6 ms 588 KB Output is correct
8 Correct 6 ms 692 KB Output is correct
9 Correct 6 ms 588 KB Output is correct
10 Correct 6 ms 588 KB Output is correct
11 Correct 635 ms 23468 KB Output is correct
12 Correct 626 ms 23776 KB Output is correct
13 Correct 598 ms 23508 KB Output is correct
14 Correct 676 ms 23528 KB Output is correct
15 Correct 649 ms 23684 KB Output is correct
16 Correct 608 ms 23708 KB Output is correct
17 Correct 639 ms 23720 KB Output is correct
18 Correct 655 ms 23496 KB Output is correct
19 Correct 618 ms 23612 KB Output is correct
20 Correct 639 ms 23604 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 7 ms 588 KB Output is correct
4 Correct 7 ms 588 KB Output is correct
5 Correct 11 ms 588 KB Output is correct
6 Correct 6 ms 588 KB Output is correct
7 Correct 6 ms 588 KB Output is correct
8 Correct 6 ms 692 KB Output is correct
9 Correct 6 ms 588 KB Output is correct
10 Correct 6 ms 588 KB Output is correct
11 Correct 635 ms 23468 KB Output is correct
12 Correct 626 ms 23776 KB Output is correct
13 Correct 598 ms 23508 KB Output is correct
14 Correct 676 ms 23528 KB Output is correct
15 Correct 649 ms 23684 KB Output is correct
16 Correct 608 ms 23708 KB Output is correct
17 Correct 639 ms 23720 KB Output is correct
18 Correct 655 ms 23496 KB Output is correct
19 Correct 618 ms 23612 KB Output is correct
20 Correct 639 ms 23604 KB Output is correct
21 Execution timed out 2581 ms 98992 KB Time limit exceeded
22 Halted 0 ms 0 KB -