oj.uz

Submission #779731

# Submission time Handle Problem Language Result Execution time Memory
779731 2023-07-11T18:00:35 Z epicci23 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 3000 ms 237952 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 40 ms 94156 KB Output is correct
2 Correct 39 ms 94192 KB Output is correct
3 Correct 39 ms 94264 KB Output is correct
4 Correct 40 ms 94256 KB Output is correct
5 Correct 40 ms 94176 KB Output is correct
6 Correct 41 ms 94236 KB Output is correct
7 Correct 40 ms 94316 KB Output is correct
8 Correct 41 ms 94312 KB Output is correct
9 Correct 45 ms 94244 KB Output is correct
10 Correct 41 ms 94264 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 94156 KB Output is correct
2 Correct 39 ms 94192 KB Output is correct
3 Correct 39 ms 94264 KB Output is correct
4 Correct 40 ms 94256 KB Output is correct
5 Correct 40 ms 94176 KB Output is correct
6 Correct 41 ms 94236 KB Output is correct
7 Correct 40 ms 94316 KB Output is correct
8 Correct 41 ms 94312 KB Output is correct
9 Correct 45 ms 94244 KB Output is correct
10 Correct 41 ms 94264 KB Output is correct
11 Correct 42 ms 94408 KB Output is correct
12 Correct 43 ms 95024 KB Output is correct
13 Correct 47 ms 94956 KB Output is correct
14 Correct 46 ms 95052 KB Output is correct
15 Correct 46 ms 95068 KB Output is correct
16 Correct 46 ms 95008 KB Output is correct
17 Correct 42 ms 94796 KB Output is correct
18 Correct 44 ms 94956 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2882 ms 237768 KB Output is correct
2 Correct 2895 ms 237952 KB Output is correct
3 Execution timed out 3004 ms 237816 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 108568 KB Output is correct
2 Correct 198 ms 108556 KB Output is correct
3 Correct 199 ms 108536 KB Output is correct
4 Correct 167 ms 108480 KB Output is correct
5 Correct 204 ms 108588 KB Output is correct
6 Correct 156 ms 108564 KB Output is correct
7 Correct 145 ms 108512 KB Output is correct
8 Correct 149 ms 108548 KB Output is correct
9 Correct 78 ms 94508 KB Output is correct
10 Correct 145 ms 108488 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 94156 KB Output is correct
2 Correct 39 ms 94192 KB Output is correct
3 Correct 39 ms 94264 KB Output is correct
4 Correct 40 ms 94256 KB Output is correct
5 Correct 40 ms 94176 KB Output is correct
6 Correct 41 ms 94236 KB Output is correct
7 Correct 40 ms 94316 KB Output is correct
8 Correct 41 ms 94312 KB Output is correct
9 Correct 45 ms 94244 KB Output is correct
10 Correct 41 ms 94264 KB Output is correct
11 Correct 42 ms 94408 KB Output is correct
12 Correct 43 ms 95024 KB Output is correct
13 Correct 47 ms 94956 KB Output is correct
14 Correct 46 ms 95052 KB Output is correct
15 Correct 46 ms 95068 KB Output is correct
16 Correct 46 ms 95008 KB Output is correct
17 Correct 42 ms 94796 KB Output is correct
18 Correct 44 ms 94956 KB Output is correct
19 Correct 476 ms 123676 KB Output is correct
20 Correct 447 ms 123612 KB Output is correct
21 Correct 353 ms 123588 KB Output is correct
22 Correct 342 ms 123664 KB Output is correct
23 Correct 339 ms 123592 KB Output is correct
24 Correct 300 ms 123564 KB Output is correct
25 Correct 293 ms 123636 KB Output is correct
26 Correct 367 ms 123616 KB Output is correct
27 Correct 408 ms 123660 KB Output is correct
28 Correct 377 ms 123680 KB Output is correct
29 Correct 369 ms 123672 KB Output is correct
30 Correct 403 ms 123648 KB Output is correct
31 Correct 391 ms 123588 KB Output is correct
32 Correct 377 ms 123648 KB Output is correct
33 Correct 391 ms 123588 KB Output is correct
34 Correct 295 ms 123608 KB Output is correct
35 Correct 307 ms 123572 KB Output is correct
36 Correct 315 ms 123584 KB Output is correct
37 Correct 278 ms 123584 KB Output is correct
38 Correct 287 ms 123616 KB Output is correct
39 Correct 337 ms 123584 KB Output is correct
40 Correct 209 ms 111300 KB Output is correct
41 Correct 309 ms 123752 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 94156 KB Output is correct
2 Correct 39 ms 94192 KB Output is correct
3 Correct 39 ms 94264 KB Output is correct
4 Correct 40 ms 94256 KB Output is correct
5 Correct 40 ms 94176 KB Output is correct
6 Correct 41 ms 94236 KB Output is correct
7 Correct 40 ms 94316 KB Output is correct
8 Correct 41 ms 94312 KB Output is correct
9 Correct 45 ms 94244 KB Output is correct
10 Correct 41 ms 94264 KB Output is correct
11 Correct 42 ms 94408 KB Output is correct
12 Correct 43 ms 95024 KB Output is correct
13 Correct 47 ms 94956 KB Output is correct
14 Correct 46 ms 95052 KB Output is correct
15 Correct 46 ms 95068 KB Output is correct
16 Correct 46 ms 95008 KB Output is correct
17 Correct 42 ms 94796 KB Output is correct
18 Correct 44 ms 94956 KB Output is correct
19 Correct 2882 ms 237768 KB Output is correct
20 Correct 2895 ms 237952 KB Output is correct
21 Execution timed out 3004 ms 237816 KB Time limit exceeded
22 Halted 0 ms 0 KB -