oj.uz

Submission #476476

# Submission time Handle Problem Language Result Execution time Memory
476476 2021-09-27T09:59:13 Z neki Index (COCI21_index) C++14
60 / 110
 2500 ms 194236 KB 
#include <bits/stdc++.h>
#define ll long long
#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() {
    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: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define loop(i, a, b) for(ll i=a;i<b;++i)
......
   63 |             loop(j, 0, tr[i].size()) while(ques[i].size() and tr[i][j]>=ques[i].back().fi){
      |                  ~~~~~~~~~~~~~~~~~~
index.cpp:63:13: note: in expansion of macro 'loop'
   63 |             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 9 ms 844 KB Output is correct
2 Correct 10 ms 952 KB Output is correct
3 Correct 9 ms 844 KB Output is correct
4 Correct 10 ms 844 KB Output is correct
5 Correct 10 ms 844 KB Output is correct
6 Correct 9 ms 956 KB Output is correct
7 Correct 9 ms 960 KB Output is correct
8 Correct 9 ms 844 KB Output is correct
9 Correct 9 ms 940 KB Output is correct
10 Correct 10 ms 844 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 844 KB Output is correct
2 Correct 10 ms 952 KB Output is correct
3 Correct 9 ms 844 KB Output is correct
4 Correct 10 ms 844 KB Output is correct
5 Correct 10 ms 844 KB Output is correct
6 Correct 9 ms 956 KB Output is correct
7 Correct 9 ms 960 KB Output is correct
8 Correct 9 ms 844 KB Output is correct
9 Correct 9 ms 940 KB Output is correct
10 Correct 10 ms 844 KB Output is correct
11 Correct 1232 ms 44384 KB Output is correct
12 Correct 1235 ms 44404 KB Output is correct
13 Correct 1249 ms 44448 KB Output is correct
14 Correct 1205 ms 44808 KB Output is correct
15 Correct 1207 ms 44404 KB Output is correct
16 Correct 1216 ms 44352 KB Output is correct
17 Correct 1222 ms 44404 KB Output is correct
18 Correct 1185 ms 44996 KB Output is correct
19 Correct 1245 ms 44320 KB Output is correct
20 Correct 1238 ms 44252 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 844 KB Output is correct
2 Correct 10 ms 952 KB Output is correct
3 Correct 9 ms 844 KB Output is correct
4 Correct 10 ms 844 KB Output is correct
5 Correct 10 ms 844 KB Output is correct
6 Correct 9 ms 956 KB Output is correct
7 Correct 9 ms 960 KB Output is correct
8 Correct 9 ms 844 KB Output is correct
9 Correct 9 ms 940 KB Output is correct
10 Correct 10 ms 844 KB Output is correct
11 Correct 1232 ms 44384 KB Output is correct
12 Correct 1235 ms 44404 KB Output is correct
13 Correct 1249 ms 44448 KB Output is correct
14 Correct 1205 ms 44808 KB Output is correct
15 Correct 1207 ms 44404 KB Output is correct
16 Correct 1216 ms 44352 KB Output is correct
17 Correct 1222 ms 44404 KB Output is correct
18 Correct 1185 ms 44996 KB Output is correct
19 Correct 1245 ms 44320 KB Output is correct
20 Correct 1238 ms 44252 KB Output is correct
21 Execution timed out 2604 ms 194236 KB Time limit exceeded
22 Halted 0 ms 0 KB -