oj.uz

Submission #476477

# Submission time Handle Problem Language Result Execution time Memory
476477 2021-09-27T10:00:17 Z neki Index (COCI21_index) C++14
60 / 110
 2500 ms 190648 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() {
    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: '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)
......
   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 9 ms 972 KB Output is correct
2 Correct 8 ms 972 KB Output is correct
3 Correct 9 ms 972 KB Output is correct
4 Correct 9 ms 844 KB Output is correct
5 Correct 8 ms 844 KB Output is correct
6 Correct 9 ms 964 KB Output is correct
7 Correct 9 ms 844 KB Output is correct
8 Correct 9 ms 968 KB Output is correct
9 Correct 9 ms 964 KB Output is correct
10 Correct 10 ms 968 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 972 KB Output is correct
2 Correct 8 ms 972 KB Output is correct
3 Correct 9 ms 972 KB Output is correct
4 Correct 9 ms 844 KB Output is correct
5 Correct 8 ms 844 KB Output is correct
6 Correct 9 ms 964 KB Output is correct
7 Correct 9 ms 844 KB Output is correct
8 Correct 9 ms 968 KB Output is correct
9 Correct 9 ms 964 KB Output is correct
10 Correct 10 ms 968 KB Output is correct
11 Correct 1187 ms 43676 KB Output is correct
12 Correct 1211 ms 43552 KB Output is correct
13 Correct 1195 ms 43816 KB Output is correct
14 Correct 1197 ms 44160 KB Output is correct
15 Correct 1167 ms 43436 KB Output is correct
16 Correct 1206 ms 43508 KB Output is correct
17 Correct 1226 ms 43528 KB Output is correct
18 Correct 1211 ms 44080 KB Output is correct
19 Correct 1218 ms 43700 KB Output is correct
20 Correct 1194 ms 43664 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 972 KB Output is correct
2 Correct 8 ms 972 KB Output is correct
3 Correct 9 ms 972 KB Output is correct
4 Correct 9 ms 844 KB Output is correct
5 Correct 8 ms 844 KB Output is correct
6 Correct 9 ms 964 KB Output is correct
7 Correct 9 ms 844 KB Output is correct
8 Correct 9 ms 968 KB Output is correct
9 Correct 9 ms 964 KB Output is correct
10 Correct 10 ms 968 KB Output is correct
11 Correct 1187 ms 43676 KB Output is correct
12 Correct 1211 ms 43552 KB Output is correct
13 Correct 1195 ms 43816 KB Output is correct
14 Correct 1197 ms 44160 KB Output is correct
15 Correct 1167 ms 43436 KB Output is correct
16 Correct 1206 ms 43508 KB Output is correct
17 Correct 1226 ms 43528 KB Output is correct
18 Correct 1211 ms 44080 KB Output is correct
19 Correct 1218 ms 43700 KB Output is correct
20 Correct 1194 ms 43664 KB Output is correct
21 Execution timed out 2587 ms 190648 KB Time limit exceeded
22 Halted 0 ms 0 KB -