oj.uz

Submission #476479

# Submission time Handle Problem Language Result Execution time Memory
476479 2021-09-27T10:05:13 Z neki Index (COCI21_index) C++14
60 / 110
 2500 ms 114976 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);
    while(1){
        ll br=1;
        loop(i, 0, q) if(l[i]<r[i]) br=0;
        if(br) break;
        
        vc<vc<par>> ques(2 * n);
        vc<ll> sum(q, 0);
        loop(i, 0, q) if(l[i]<r[i]){
            ll mid=(l[i]+r[i]+1)/2;
            fore(v, prno[i]) ques[v].eb(mid, i);
        }
        
        loop(i, 1, 2 * n) if(ques[i].size()){
            sort(all(ques[i]), greater<par>());
            loop(j, 0, tr[i].size()) while(ques[i].size() and tr[i][j]>=ques[i].back().fi){
                sum[ques[i].back().se]+=tr[i].size()-j;
                ques[i].pop_back();
            } 
        }
        
        loop(i, 0, q) if(l[i]<r[i]){
            ll mid=(l[i]+r[i]+1)/2;
            if(mid<=sum[i]) l[i]=mid;
            else r[i]=mid-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)
......
   65 |             loop(j, 0, tr[i].size()) while(ques[i].size() and tr[i][j]>=ques[i].back().fi){
      |                  ~~~~~~~~~~~~~~~~~~
index.cpp:65:13: note: in expansion of macro 'loop'
   65 |             loop(j, 0, tr[i].size()) while(ques[i].size() and tr[i][j]>=ques[i].back().fi){
      |             ^~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 716 KB Output is correct
2 Correct 8 ms 740 KB Output is correct
3 Correct 9 ms 716 KB Output is correct
4 Correct 9 ms 716 KB Output is correct
5 Correct 9 ms 716 KB Output is correct
6 Correct 9 ms 736 KB Output is correct
7 Correct 9 ms 716 KB Output is correct
8 Correct 8 ms 716 KB Output is correct
9 Correct 10 ms 716 KB Output is correct
10 Correct 10 ms 736 KB Output is correct
11 Correct 1131 ms 26932 KB Output is correct
12 Correct 1135 ms 27148 KB Output is correct
13 Correct 1132 ms 27196 KB Output is correct
14 Correct 1146 ms 27744 KB Output is correct
15 Correct 1113 ms 28676 KB Output is correct
16 Correct 1101 ms 27688 KB Output is correct
17 Correct 1083 ms 26796 KB Output is correct
18 Correct 1150 ms 27032 KB Output is correct
19 Correct 1099 ms 27952 KB Output is correct
20 Correct 1108 ms 26852 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 716 KB Output is correct
2 Correct 8 ms 740 KB Output is correct
3 Correct 9 ms 716 KB Output is correct
4 Correct 9 ms 716 KB Output is correct
5 Correct 9 ms 716 KB Output is correct
6 Correct 9 ms 736 KB Output is correct
7 Correct 9 ms 716 KB Output is correct
8 Correct 8 ms 716 KB Output is correct
9 Correct 10 ms 716 KB Output is correct
10 Correct 10 ms 736 KB Output is correct
11 Correct 1131 ms 26932 KB Output is correct
12 Correct 1135 ms 27148 KB Output is correct
13 Correct 1132 ms 27196 KB Output is correct
14 Correct 1146 ms 27744 KB Output is correct
15 Correct 1113 ms 28676 KB Output is correct
16 Correct 1101 ms 27688 KB Output is correct
17 Correct 1083 ms 26796 KB Output is correct
18 Correct 1150 ms 27032 KB Output is correct
19 Correct 1099 ms 27952 KB Output is correct
20 Correct 1108 ms 26852 KB Output is correct
21 Execution timed out 2605 ms 114976 KB Time limit exceeded
22 Halted 0 ms 0 KB -