oj.uz

Submission #779724

# Submission time Handle Problem Language Result Execution time Memory
779724 2023-07-11T17:33:25 Z epicci23 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 539 ms 262144 KB 
#include "bits/stdc++.h"
#pragma optimize ("Bismillahirrahmanirrahim")
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define endl "\n" 
#define int long long
#define double long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define what_is(x) cerr << #x << " is " << x << endl;
#define m (l+r)/2
constexpr int N=1000005;
constexpr int MOD=1000000007;
constexpr int  INF2 = LLONG_MAX;
constexpr int INF=(int)1e18;
constexpr int LOG=30;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
typedef priority_queue<pii,vector<pii>,greater<pii>> min_pq;
typedef priority_queue<pii> max_pq;
typedef long long ll;
//to think//
/*
 * graph approach
 * dp
 * dividing the problem to smaller statements
 * finding the real constraint
 * sqrt decomposition
 * greedy approach
 * pigeonhole principle
 * rewriting the problem/equality 
 * bitwise approaches
 * binary search if monotonic
 * divide and conquer
 * combinatorics
 * inclusion - exclusion
 * think like bfs
*/



inline int in()
{
  int x;cin >> x;
  return x;
}

inline string in2()
{
  string x;cin >> x;
  return x;
}

vector<int> seg[4*N];
int ans[4*N];
int ar[N];
int n,q;
int maxi=0;
vector<int> xd;
void build(int rt,int l,int r)
{
  if(l==r) {seg[rt].pb(ar[l]);return;}
  build(rt*2,l,m);build(rt*2+1,m+1,r);
  ans[rt]=max(ans[rt*2],ans[rt*2+1]);
  int it=lower_bound(all(seg[rt*2+1]),seg[rt*2].back())-seg[rt*2+1].begin();
  if(it) ans[rt]=max(seg[rt*2].back()+seg[rt*2+1][it-1],ans[rt]);
  
  int n1=sz(seg[rt*2]),m1=sz(seg[rt*2+1]);
  int p1=0,p2=0;
  while(p1<n1 && p2<m1)
  {
    if(seg[rt*2][p1]<=seg[rt*2+1][p2]) seg[rt].pb(seg[rt*2][p1++]);
    else seg[rt].pb(seg[rt*2+1][p2++]);
  }
  while(p1<n1) seg[rt].pb(seg[rt*2][p1++]);
  while(p2<m1) seg[rt].pb(seg[rt*2+1][p2++]);
}

void query(int rt,int l,int r,int gl,int gr)
{
  if(r<gl || l>gr || l>r) return;
  if(l>=gl && r<=gr)
  {
    maxi=max(maxi,ans[rt]);
    xd.pb(rt);
    return;
  } 
  query(rt*2,l,m,gl,gr);query(rt*2+1,m+1,r,gl,gr);
}


void solve()
{
  n=in(),q=in();
  for(int i=1;i<=n;i++) ar[i]=in();
  build(1,1,n);

  while(q--)
  {
    maxi=0;
    xd.clear();
    int l=in(),r=in(),zo=in();
    query(1,1,n,l,r);
    int hm=0;
    for(int i=0;i<sz(xd)-1;i++)
    {
      hm=max(hm,seg[xd[i]].back());
      int it=lower_bound(all(seg[xd[i+1]]),hm)-seg[xd[i+1]].begin();
      if(it) maxi=max(hm+seg[xd[i+1]][it-1],maxi);
    }

    if(maxi<=zo) cout << 1 << endl;
    else cout << 0 << endl;
  }
} 

int32_t main(){
   

     cin.tie(0); ios::sync_with_stdio(0);
     cout << fixed <<  setprecision(15);
   
   int t=1;//cin>> t;
 
 for(int i=1;i<=t;i++)
 {
  //  cout << "Case #" << i << ": ";
    solve();
 }
 
 return 0;
}

Compilation message

sortbooks.cpp:2: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    2 | #pragma optimize ("Bismillahirrahmanirrahim")
      |

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94176 KB Output is correct
2 Correct 51 ms 94228 KB Output is correct
3 Correct 43 ms 94256 KB Output is correct
4 Correct 44 ms 94276 KB Output is correct
5 Correct 46 ms 94268 KB Output is correct
6 Correct 46 ms 94324 KB Output is correct
7 Correct 41 ms 94248 KB Output is correct
8 Correct 42 ms 94316 KB Output is correct
9 Correct 44 ms 94232 KB Output is correct
10 Correct 51 ms 94264 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94176 KB Output is correct
2 Correct 51 ms 94228 KB Output is correct
3 Correct 43 ms 94256 KB Output is correct
4 Correct 44 ms 94276 KB Output is correct
5 Correct 46 ms 94268 KB Output is correct
6 Correct 46 ms 94324 KB Output is correct
7 Correct 41 ms 94248 KB Output is correct
8 Correct 42 ms 94316 KB Output is correct
9 Correct 44 ms 94232 KB Output is correct
10 Correct 51 ms 94264 KB Output is correct
11 Correct 45 ms 94564 KB Output is correct
12 Correct 52 ms 95340 KB Output is correct
13 Correct 50 ms 95460 KB Output is correct
14 Correct 50 ms 95496 KB Output is correct
15 Correct 52 ms 95472 KB Output is correct
16 Correct 48 ms 95404 KB Output is correct
17 Correct 47 ms 95044 KB Output is correct
18 Correct 56 ms 95460 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 379 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 117816 KB Output is correct
2 Correct 197 ms 118216 KB Output is correct
3 Correct 201 ms 118112 KB Output is correct
4 Correct 191 ms 118224 KB Output is correct
5 Correct 199 ms 118152 KB Output is correct
6 Correct 167 ms 118208 KB Output is correct
7 Correct 156 ms 118180 KB Output is correct
8 Correct 176 ms 118340 KB Output is correct
9 Correct 78 ms 95560 KB Output is correct
10 Correct 170 ms 118188 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94176 KB Output is correct
2 Correct 51 ms 94228 KB Output is correct
3 Correct 43 ms 94256 KB Output is correct
4 Correct 44 ms 94276 KB Output is correct
5 Correct 46 ms 94268 KB Output is correct
6 Correct 46 ms 94324 KB Output is correct
7 Correct 41 ms 94248 KB Output is correct
8 Correct 42 ms 94316 KB Output is correct
9 Correct 44 ms 94232 KB Output is correct
10 Correct 51 ms 94264 KB Output is correct
11 Correct 45 ms 94564 KB Output is correct
12 Correct 52 ms 95340 KB Output is correct
13 Correct 50 ms 95460 KB Output is correct
14 Correct 50 ms 95496 KB Output is correct
15 Correct 52 ms 95472 KB Output is correct
16 Correct 48 ms 95404 KB Output is correct
17 Correct 47 ms 95044 KB Output is correct
18 Correct 56 ms 95460 KB Output is correct
19 Correct 499 ms 142816 KB Output is correct
20 Correct 498 ms 142808 KB Output is correct
21 Correct 421 ms 142808 KB Output is correct
22 Correct 388 ms 142784 KB Output is correct
23 Correct 361 ms 142724 KB Output is correct
24 Correct 304 ms 142796 KB Output is correct
25 Correct 389 ms 142860 KB Output is correct
26 Correct 539 ms 142784 KB Output is correct
27 Correct 489 ms 142800 KB Output is correct
28 Correct 421 ms 142832 KB Output is correct
29 Correct 437 ms 142780 KB Output is correct
30 Correct 451 ms 142872 KB Output is correct
31 Correct 513 ms 142796 KB Output is correct
32 Correct 451 ms 142832 KB Output is correct
33 Correct 474 ms 142908 KB Output is correct
34 Correct 297 ms 142784 KB Output is correct
35 Correct 320 ms 142780 KB Output is correct
36 Correct 308 ms 142772 KB Output is correct
37 Correct 309 ms 142800 KB Output is correct
38 Correct 306 ms 142784 KB Output is correct
39 Correct 400 ms 142904 KB Output is correct
40 Correct 288 ms 121872 KB Output is correct
41 Correct 357 ms 142828 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94176 KB Output is correct
2 Correct 51 ms 94228 KB Output is correct
3 Correct 43 ms 94256 KB Output is correct
4 Correct 44 ms 94276 KB Output is correct
5 Correct 46 ms 94268 KB Output is correct
6 Correct 46 ms 94324 KB Output is correct
7 Correct 41 ms 94248 KB Output is correct
8 Correct 42 ms 94316 KB Output is correct
9 Correct 44 ms 94232 KB Output is correct
10 Correct 51 ms 94264 KB Output is correct
11 Correct 45 ms 94564 KB Output is correct
12 Correct 52 ms 95340 KB Output is correct
13 Correct 50 ms 95460 KB Output is correct
14 Correct 50 ms 95496 KB Output is correct
15 Correct 52 ms 95472 KB Output is correct
16 Correct 48 ms 95404 KB Output is correct
17 Correct 47 ms 95044 KB Output is correct
18 Correct 56 ms 95460 KB Output is correct
19 Runtime error 379 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -