oj.uz

Submission #476482

# Submission time Handle Problem Language Result Execution time Memory
476482 2021-09-27T10:14:26 Z neki Index (COCI21_index) C++14
60 / 110
 2500 ms 99608 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());
    
    /*loop(i, 1, 2 * n){
        cout << i <<": ";
        fore(v, tr[i]) cout << v<<" ";cout << endl;
    }
    cout << endl;*/
    
    vc<vc<ll>> prno(q);
    loop(i, 0, q){
        ll l, r;cin >> l >> r;--l;
        for(l+=n, r+=n;l<r;l>>=1, r>>=1){
            if(l&1) prno[i].ps(l++);
            if(r&1) prno[i].ps(--r);
        }
        //fore(v, prno[i]) cout << v<<" ";cout <<endl;
    }
    
    vc<ll> l(q, 0), 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) 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)
......
   64 |             loop(j, 0, tr[i].size()) while(ques[i].size() and tr[i][j]>=mid[ques[i].back()]){
      |                  ~~~~~~~~~~~~~~~~~~
index.cpp:64:13: note: in expansion of macro 'loop'
   64 |             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 5 ms 588 KB Output is correct
3 Correct 6 ms 588 KB Output is correct
4 Correct 5 ms 588 KB Output is correct
5 Correct 8 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 5 ms 588 KB Output is correct
9 Correct 5 ms 588 KB Output is correct
10 Correct 5 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 5 ms 588 KB Output is correct
3 Correct 6 ms 588 KB Output is correct
4 Correct 5 ms 588 KB Output is correct
5 Correct 8 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 5 ms 588 KB Output is correct
9 Correct 5 ms 588 KB Output is correct
10 Correct 5 ms 588 KB Output is correct
11 Correct 531 ms 23724 KB Output is correct
12 Correct 541 ms 23664 KB Output is correct
13 Correct 525 ms 23780 KB Output is correct
14 Correct 538 ms 23596 KB Output is correct
15 Correct 546 ms 23540 KB Output is correct
16 Correct 567 ms 23652 KB Output is correct
17 Correct 536 ms 23568 KB Output is correct
18 Correct 580 ms 23516 KB Output is correct
19 Correct 526 ms 23596 KB Output is correct
20 Correct 554 ms 23668 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 5 ms 588 KB Output is correct
3 Correct 6 ms 588 KB Output is correct
4 Correct 5 ms 588 KB Output is correct
5 Correct 8 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 5 ms 588 KB Output is correct
9 Correct 5 ms 588 KB Output is correct
10 Correct 5 ms 588 KB Output is correct
11 Correct 531 ms 23724 KB Output is correct
12 Correct 541 ms 23664 KB Output is correct
13 Correct 525 ms 23780 KB Output is correct
14 Correct 538 ms 23596 KB Output is correct
15 Correct 546 ms 23540 KB Output is correct
16 Correct 567 ms 23652 KB Output is correct
17 Correct 536 ms 23568 KB Output is correct
18 Correct 580 ms 23516 KB Output is correct
19 Correct 526 ms 23596 KB Output is correct
20 Correct 554 ms 23668 KB Output is correct
21 Execution timed out 2595 ms 99608 KB Time limit exceeded
22 Halted 0 ms 0 KB -