oj.uz

Submission #573433

# Submission time Handle Problem Language Result Execution time Memory
573433 2022-06-06T15:25:48 Z MohammadAghil Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
100 / 100
 1298 ms 83028 KB 
      #include <bits/stdc++.h>
  // #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
    using namespace std;
  typedef long long ll;
   typedef pair<int, int> pp;
    #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
      #define per(i,r,l) for(int i = (r); i >= (l); i--)
        #define rep(i,l,r) for(int i = (l); i < (r); i++)
           #define all(x) x.begin(), x.end()
              #define sz(x) (int)(x).size()
                  #define pb push_back
                      #define ss second
                           #define ff first
                                   void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 1e6 + 5, lg = 22, lng = 26, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}

int seg[maxn<<2], n;
int upd(int i, int k, int x = 1, int lx = 0, int rx = n){
     if(lx + 1 == rx) return seg[x] = max(seg[x], k);
     int mid = (lx + rx)>>1;
     if(i < mid) upd(i, k, x<<1, lx, mid);
     else upd(i, k, x<<1|1, mid, rx);
     return seg[x] = max(seg[x<<1], seg[x<<1|1]);
}
int get(int l, int r, int x = 1, int lx = 0, int rx = n){
     if(l <= lx && r >= rx) return seg[x];
     if(l >= rx || r <= lx) return -1;
     int mid = (lx + rx)>>1;
     return max(get(l, r, x<<1, lx, mid), get(l, r, x<<1|1, mid, rx));
}

int main(){
     cin.tie(0) -> sync_with_stdio(0);
     int q; cin >> n >> q;
     vector<int> w(n);
     rep(i,0,n){
          cin >> w[i];
     }
     struct tr{
          int r, id, k;
     };
     vector<vector<tr>> query(n);
     rep(i,0,q){
          int l, r, k; cin >> l >> r >> k; l--;
          query[l].pb({r, i, k});
     }
     fill(seg, seg+(n<<2), -1);
     vector<int> st;
     vector<bool> ans(q);
     per(i,n-1,0){
          while(sz(st) && w[st.back()] < w[i]){
               upd(st.back(), w[st.back()] + w[i]);
               st.pop_back();
          }
          st.pb(i);
          for(auto[r, id, k]: query[i]){
               ans[id] = get(i, r) <= k;
          }
     }
     for(auto c: ans) cout << c << '\n';
     return 0; 
}

/*
5 2
3 5 1 8 2
1 3 6
2 5 3
*/

Compilation message

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:59:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |           for(auto[r, id, k]: query[i]){
      |                   ^

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 3 ms 600 KB Output is correct
13 Correct 4 ms 736 KB Output is correct
14 Correct 5 ms 724 KB Output is correct
15 Correct 6 ms 724 KB Output is correct
16 Correct 4 ms 724 KB Output is correct
17 Correct 3 ms 728 KB Output is correct
18 Correct 3 ms 728 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1281 ms 70328 KB Output is correct
2 Correct 1279 ms 83028 KB Output is correct
3 Correct 1279 ms 82856 KB Output is correct
4 Correct 1228 ms 81988 KB Output is correct
5 Correct 1105 ms 74648 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 9092 KB Output is correct
2 Correct 80 ms 8780 KB Output is correct
3 Correct 78 ms 9408 KB Output is correct
4 Correct 81 ms 9540 KB Output is correct
5 Correct 80 ms 9620 KB Output is correct
6 Correct 62 ms 8792 KB Output is correct
7 Correct 62 ms 8804 KB Output is correct
8 Correct 68 ms 8700 KB Output is correct
9 Correct 36 ms 3324 KB Output is correct
10 Correct 69 ms 8708 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 3 ms 600 KB Output is correct
13 Correct 4 ms 736 KB Output is correct
14 Correct 5 ms 724 KB Output is correct
15 Correct 6 ms 724 KB Output is correct
16 Correct 4 ms 724 KB Output is correct
17 Correct 3 ms 728 KB Output is correct
18 Correct 3 ms 728 KB Output is correct
19 Correct 208 ms 20436 KB Output is correct
20 Correct 223 ms 20436 KB Output is correct
21 Correct 183 ms 19816 KB Output is correct
22 Correct 180 ms 19804 KB Output is correct
23 Correct 189 ms 19784 KB Output is correct
24 Correct 156 ms 20532 KB Output is correct
25 Correct 158 ms 20560 KB Output is correct
26 Correct 182 ms 20800 KB Output is correct
27 Correct 179 ms 20936 KB Output is correct
28 Correct 179 ms 20868 KB Output is correct
29 Correct 200 ms 21308 KB Output is correct
30 Correct 192 ms 21252 KB Output is correct
31 Correct 188 ms 21192 KB Output is correct
32 Correct 201 ms 21312 KB Output is correct
33 Correct 205 ms 21224 KB Output is correct
34 Correct 153 ms 19772 KB Output is correct
35 Correct 168 ms 19828 KB Output is correct
36 Correct 146 ms 19660 KB Output is correct
37 Correct 143 ms 19640 KB Output is correct
38 Correct 143 ms 19844 KB Output is correct
39 Correct 160 ms 19332 KB Output is correct
40 Correct 126 ms 15036 KB Output is correct
41 Correct 162 ms 18608 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 3 ms 600 KB Output is correct
13 Correct 4 ms 736 KB Output is correct
14 Correct 5 ms 724 KB Output is correct
15 Correct 6 ms 724 KB Output is correct
16 Correct 4 ms 724 KB Output is correct
17 Correct 3 ms 728 KB Output is correct
18 Correct 3 ms 728 KB Output is correct
19 Correct 1281 ms 70328 KB Output is correct
20 Correct 1279 ms 83028 KB Output is correct
21 Correct 1279 ms 82856 KB Output is correct
22 Correct 1228 ms 81988 KB Output is correct
23 Correct 1105 ms 74648 KB Output is correct
24 Correct 87 ms 9092 KB Output is correct
25 Correct 80 ms 8780 KB Output is correct
26 Correct 78 ms 9408 KB Output is correct
27 Correct 81 ms 9540 KB Output is correct
28 Correct 80 ms 9620 KB Output is correct
29 Correct 62 ms 8792 KB Output is correct
30 Correct 62 ms 8804 KB Output is correct
31 Correct 68 ms 8700 KB Output is correct
32 Correct 36 ms 3324 KB Output is correct
33 Correct 69 ms 8708 KB Output is correct
34 Correct 208 ms 20436 KB Output is correct
35 Correct 223 ms 20436 KB Output is correct
36 Correct 183 ms 19816 KB Output is correct
37 Correct 180 ms 19804 KB Output is correct
38 Correct 189 ms 19784 KB Output is correct
39 Correct 156 ms 20532 KB Output is correct
40 Correct 158 ms 20560 KB Output is correct
41 Correct 182 ms 20800 KB Output is correct
42 Correct 179 ms 20936 KB Output is correct
43 Correct 179 ms 20868 KB Output is correct
44 Correct 200 ms 21308 KB Output is correct
45 Correct 192 ms 21252 KB Output is correct
46 Correct 188 ms 21192 KB Output is correct
47 Correct 201 ms 21312 KB Output is correct
48 Correct 205 ms 21224 KB Output is correct
49 Correct 153 ms 19772 KB Output is correct
50 Correct 168 ms 19828 KB Output is correct
51 Correct 146 ms 19660 KB Output is correct
52 Correct 143 ms 19640 KB Output is correct
53 Correct 143 ms 19844 KB Output is correct
54 Correct 160 ms 19332 KB Output is correct
55 Correct 126 ms 15036 KB Output is correct
56 Correct 162 ms 18608 KB Output is correct
57 Correct 1298 ms 71624 KB Output is correct
58 Correct 1258 ms 71588 KB Output is correct
59 Correct 1180 ms 69416 KB Output is correct
60 Correct 1170 ms 69560 KB Output is correct
61 Correct 1180 ms 69508 KB Output is correct
62 Correct 1185 ms 69452 KB Output is correct
63 Correct 768 ms 69300 KB Output is correct
64 Correct 779 ms 69268 KB Output is correct
65 Correct 1046 ms 73380 KB Output is correct
66 Correct 1055 ms 72616 KB Output is correct
67 Correct 1045 ms 72520 KB Output is correct
68 Correct 1128 ms 75500 KB Output is correct
69 Correct 1122 ms 75316 KB Output is correct
70 Correct 1138 ms 73656 KB Output is correct
71 Correct 1102 ms 73888 KB Output is correct
72 Correct 1107 ms 74944 KB Output is correct
73 Correct 698 ms 68128 KB Output is correct
74 Correct 744 ms 68104 KB Output is correct
75 Correct 694 ms 67064 KB Output is correct
76 Correct 700 ms 66836 KB Output is correct
77 Correct 709 ms 67132 KB Output is correct
78 Correct 931 ms 70068 KB Output is correct
79 Correct 687 ms 46196 KB Output is correct
80 Correct 922 ms 68720 KB Output is correct