oj.uz

Submission #707134

# Submission time Handle Problem Language Result Execution time Memory
707134 2023-03-08T13:46:02 Z Karuk Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
77 / 100
 3000 ms 222908 KB 
#include<bits/stdc++.h>///3:27- func start///3:41 end
using namespace std;
vector<vector<int>>st;
int score[4000000];
int k=1;
vector<int>ind;
int max(int a,int b) {
    return a>b?a:b;
}
void push(int from,int to,int cur=1,int beg=0,int en=k-1) {
    if(from>en || to<beg)return;
    if(from<=beg && en<=to){ind.push_back(cur);return;}
    int mid=(beg+en)/2;
    push(from,to,cur*2,beg,mid);
    push(from,to,cur*2+1,mid+1,en);
}
int combine(int i,int j) {
    if(st[j].size()==0 || st[i].size()==0)return score[i];
    int mx=st[i].back();
    int ans=max(score[i],score[j]);
    int ind=lower_bound(st[j].begin(),st[j].end(),mx)-st[j].begin();
    ind--;
    if(ind>=0)ans=max(ans,mx+st[j][ind]);
    return ans;
}
int maxw(int l,int r) {
    ind.clear();
    push(l,r);
    int ans=score[ind.back()];
    int maxind=0;
    for(int i=1;i<ind.size();i++) {
        ans=max(ans,combine(ind[maxind],ind[i]));
        if(st[ind[i]].back()>st[ind[maxind]].back())maxind=i;
    }
    return ans;
}
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,m;cin>>n>>m;
    int a[n];
    for(int i=0;i<n;i++)cin>>a[i];
    while(k<n){k<<=1;}
    st.resize(k*2+1);
    for(int i=0;i<n;i++)st[i+k].push_back(a[i]);
    for(int i=k-1;i>0;i--) {
        int p1=0,p2=0;
        while(p1<st[i*2].size() && p2<st[i*2+1].size()) {
            if(st[i*2][p1]<st[i*2+1][p2]) {
                st[i].push_back(st[i*2][p1]);
                p1++;
            } else {
                st[i].push_back(st[i*2+1][p2]);
                p2++;
            }
        }
        while(p1<st[i*2].size()) {
            st[i].push_back(st[i*2][p1]);
            p1++;
        }
        while(p2<st[i*2+1].size()) {
            st[i].push_back(st[i*2+1][p2]);
            p2++;
        }
        score[i]=combine(2*i,2*i+1);
    }
    for(int i=0;i<m;i++) {
        int l,r,w;cin>>l>>r>>w;
        l--;r--;
        int as=maxw(l,r);
        if(as<=w)cout<<1<<'\n';
        else cout<<0<<'\n';
    }
    return 0;
}
/**
5 6
3 2 9 8 1
*/

Compilation message

sortbooks.cpp: In function 'int maxw(int, int)':
sortbooks.cpp:31:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int i=1;i<ind.size();i++) {
      |                 ~^~~~~~~~~~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:47:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         while(p1<st[i*2].size() && p2<st[i*2+1].size()) {
      |               ~~^~~~~~~~~~~~~~~
sortbooks.cpp:47:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         while(p1<st[i*2].size() && p2<st[i*2+1].size()) {
      |                                    ~~^~~~~~~~~~~~~~~~~
sortbooks.cpp:56:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         while(p1<st[i*2].size()) {
      |               ~~^~~~~~~~~~~~~~~
sortbooks.cpp:60:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         while(p2<st[i*2+1].size()) {
      |               ~~^~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 5 ms 1348 KB Output is correct
13 Correct 5 ms 1364 KB Output is correct
14 Correct 7 ms 1364 KB Output is correct
15 Correct 7 ms 1360 KB Output is correct
16 Correct 5 ms 1432 KB Output is correct
17 Correct 4 ms 1076 KB Output is correct
18 Correct 5 ms 1368 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2875 ms 189268 KB Output is correct
2 Correct 2955 ms 191104 KB Output is correct
3 Correct 2882 ms 189316 KB Output is correct
4 Correct 2934 ms 191072 KB Output is correct
5 Correct 2536 ms 222172 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 19628 KB Output is correct
2 Correct 164 ms 21548 KB Output is correct
3 Correct 168 ms 21632 KB Output is correct
4 Correct 162 ms 21560 KB Output is correct
5 Correct 158 ms 21712 KB Output is correct
6 Correct 121 ms 21360 KB Output is correct
7 Correct 127 ms 21476 KB Output is correct
8 Correct 137 ms 21244 KB Output is correct
9 Correct 38 ms 1868 KB Output is correct
10 Correct 134 ms 21188 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 5 ms 1348 KB Output is correct
13 Correct 5 ms 1364 KB Output is correct
14 Correct 7 ms 1364 KB Output is correct
15 Correct 7 ms 1360 KB Output is correct
16 Correct 5 ms 1432 KB Output is correct
17 Correct 4 ms 1076 KB Output is correct
18 Correct 5 ms 1368 KB Output is correct
19 Correct 457 ms 45924 KB Output is correct
20 Correct 451 ms 46144 KB Output is correct
21 Correct 390 ms 45856 KB Output is correct
22 Correct 359 ms 45824 KB Output is correct
23 Correct 343 ms 45812 KB Output is correct
24 Correct 311 ms 45800 KB Output is correct
25 Correct 279 ms 45664 KB Output is correct
26 Correct 375 ms 45940 KB Output is correct
27 Correct 383 ms 45880 KB Output is correct
28 Correct 398 ms 45928 KB Output is correct
29 Correct 398 ms 46032 KB Output is correct
30 Correct 379 ms 45960 KB Output is correct
31 Correct 467 ms 45932 KB Output is correct
32 Correct 396 ms 45992 KB Output is correct
33 Correct 386 ms 45944 KB Output is correct
34 Correct 277 ms 45548 KB Output is correct
35 Correct 277 ms 45640 KB Output is correct
36 Correct 275 ms 45440 KB Output is correct
37 Correct 319 ms 45412 KB Output is correct
38 Correct 278 ms 45540 KB Output is correct
39 Correct 354 ms 44544 KB Output is correct
40 Correct 215 ms 27924 KB Output is correct
41 Correct 315 ms 44164 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 5 ms 1348 KB Output is correct
13 Correct 5 ms 1364 KB Output is correct
14 Correct 7 ms 1364 KB Output is correct
15 Correct 7 ms 1360 KB Output is correct
16 Correct 5 ms 1432 KB Output is correct
17 Correct 4 ms 1076 KB Output is correct
18 Correct 5 ms 1368 KB Output is correct
19 Correct 2875 ms 189268 KB Output is correct
20 Correct 2955 ms 191104 KB Output is correct
21 Correct 2882 ms 189316 KB Output is correct
22 Correct 2934 ms 191072 KB Output is correct
23 Correct 2536 ms 222172 KB Output is correct
24 Correct 214 ms 19628 KB Output is correct
25 Correct 164 ms 21548 KB Output is correct
26 Correct 168 ms 21632 KB Output is correct
27 Correct 162 ms 21560 KB Output is correct
28 Correct 158 ms 21712 KB Output is correct
29 Correct 121 ms 21360 KB Output is correct
30 Correct 127 ms 21476 KB Output is correct
31 Correct 137 ms 21244 KB Output is correct
32 Correct 38 ms 1868 KB Output is correct
33 Correct 134 ms 21188 KB Output is correct
34 Correct 457 ms 45924 KB Output is correct
35 Correct 451 ms 46144 KB Output is correct
36 Correct 390 ms 45856 KB Output is correct
37 Correct 359 ms 45824 KB Output is correct
38 Correct 343 ms 45812 KB Output is correct
39 Correct 311 ms 45800 KB Output is correct
40 Correct 279 ms 45664 KB Output is correct
41 Correct 375 ms 45940 KB Output is correct
42 Correct 383 ms 45880 KB Output is correct
43 Correct 398 ms 45928 KB Output is correct
44 Correct 398 ms 46032 KB Output is correct
45 Correct 379 ms 45960 KB Output is correct
46 Correct 467 ms 45932 KB Output is correct
47 Correct 396 ms 45992 KB Output is correct
48 Correct 386 ms 45944 KB Output is correct
49 Correct 277 ms 45548 KB Output is correct
50 Correct 277 ms 45640 KB Output is correct
51 Correct 275 ms 45440 KB Output is correct
52 Correct 319 ms 45412 KB Output is correct
53 Correct 278 ms 45540 KB Output is correct
54 Correct 354 ms 44544 KB Output is correct
55 Correct 215 ms 27924 KB Output is correct
56 Correct 315 ms 44164 KB Output is correct
57 Execution timed out 3018 ms 222908 KB Time limit exceeded
58 Halted 0 ms 0 KB -