oj.uz

Submission #489603

# Submission time Handle Problem Language Result Execution time Memory
489603 2021-11-23T10:52:41 Z cpp219 Index (COCI21_index) C++14
110 / 110
 620 ms 41000 KB 
#include<bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
#define debug(y) cout<<y,exit(0)
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 2e5 + 9;
const ll inf = 1e9 + 7;

vector<ll> g[N],num[N];
ll n,Q,a[N],l[N],h[N],bit[N];
LL q[N];

void upd(ll p,ll val){
    for (ll i = p;i <= n;i += i & -i) bit[i] += val;
}
ll Get(ll p){
    ll res = 0;
    for (ll i = p;i > 0;i -= i & -i) res += bit[i];
    return res;
}
ll Query(ll l,ll r){
    return Get(r) - Get(l - 1);
}

int main(){
    ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    #define task "tst"
    if (fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        //freopen(task".out","w",stdout);
    }
    cin>>n>>Q;
    for (ll i = 1;i <= n;i++) cin>>a[i],num[a[i]].push_back(i);
    for (ll i = 1;i <= Q;i++){
        cin>>q[i].fs>>q[i].sc;
        l[i] = 1; h[i] = n;
    }
    while(1){
        bool flag = 0; memset(bit,0,sizeof(bit));
        for (ll i = 1;i <= Q;i++){
            ll mid = (l[i] + h[i])/2;
            if (l[i] <= h[i])
                g[mid].push_back(i),flag = 1;
        }
        if (!flag) break;
        for (ll i = N - 1;i > 0;i--){
            for (auto j : num[i]) upd(j,1);
            for (auto j : g[i]){
                //debug(Query(q[j].fs,q[j].sc));
                if (Query(q[j].fs,q[j].sc) >= i) l[j] = i + 1;
                else h[j] = i - 1;
            }
            g[i].clear();
        }
    }
    for (ll i = 1;i <= Q;i++) cout<<h[i]<<"\n";
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

Compilation message

index.cpp: In function 'int main()':
index.cpp:32:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 10752 KB Output is correct
2 Correct 13 ms 10616 KB Output is correct
3 Correct 13 ms 10576 KB Output is correct
4 Correct 13 ms 10604 KB Output is correct
5 Correct 13 ms 10576 KB Output is correct
6 Correct 15 ms 10592 KB Output is correct
7 Correct 13 ms 10620 KB Output is correct
8 Correct 14 ms 10576 KB Output is correct
9 Correct 13 ms 10624 KB Output is correct
10 Correct 13 ms 10592 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 10752 KB Output is correct
2 Correct 13 ms 10616 KB Output is correct
3 Correct 13 ms 10576 KB Output is correct
4 Correct 13 ms 10604 KB Output is correct
5 Correct 13 ms 10576 KB Output is correct
6 Correct 15 ms 10592 KB Output is correct
7 Correct 13 ms 10620 KB Output is correct
8 Correct 14 ms 10576 KB Output is correct
9 Correct 13 ms 10624 KB Output is correct
10 Correct 13 ms 10592 KB Output is correct
11 Correct 131 ms 17476 KB Output is correct
12 Correct 117 ms 17396 KB Output is correct
13 Correct 114 ms 17356 KB Output is correct
14 Correct 109 ms 17488 KB Output is correct
15 Correct 123 ms 17300 KB Output is correct
16 Correct 109 ms 17412 KB Output is correct
17 Correct 109 ms 17484 KB Output is correct
18 Correct 122 ms 17504 KB Output is correct
19 Correct 117 ms 17376 KB Output is correct
20 Correct 110 ms 17424 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 10752 KB Output is correct
2 Correct 13 ms 10616 KB Output is correct
3 Correct 13 ms 10576 KB Output is correct
4 Correct 13 ms 10604 KB Output is correct
5 Correct 13 ms 10576 KB Output is correct
6 Correct 15 ms 10592 KB Output is correct
7 Correct 13 ms 10620 KB Output is correct
8 Correct 14 ms 10576 KB Output is correct
9 Correct 13 ms 10624 KB Output is correct
10 Correct 13 ms 10592 KB Output is correct
11 Correct 131 ms 17476 KB Output is correct
12 Correct 117 ms 17396 KB Output is correct
13 Correct 114 ms 17356 KB Output is correct
14 Correct 109 ms 17488 KB Output is correct
15 Correct 123 ms 17300 KB Output is correct
16 Correct 109 ms 17412 KB Output is correct
17 Correct 109 ms 17484 KB Output is correct
18 Correct 122 ms 17504 KB Output is correct
19 Correct 117 ms 17376 KB Output is correct
20 Correct 110 ms 17424 KB Output is correct
21 Correct 594 ms 40684 KB Output is correct
22 Correct 607 ms 40744 KB Output is correct
23 Correct 620 ms 40636 KB Output is correct
24 Correct 597 ms 40656 KB Output is correct
25 Correct 566 ms 41000 KB Output is correct
26 Correct 580 ms 40696 KB Output is correct
27 Correct 593 ms 40544 KB Output is correct
28 Correct 547 ms 40768 KB Output is correct
29 Correct 562 ms 40664 KB Output is correct
30 Correct 581 ms 40492 KB Output is correct