oj.uz

Submission #899132

# Submission time Handle Problem Language Result Execution time Memory
899132 2024-01-05T13:55:47 Z Nika533 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
0 / 100
 2137 ms 98588 KB 
#pragma gcc diagnostic "-std=c++1z"
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define f first
#define s second
#define MOD 1000000007
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()

using namespace std;

const int N=1e6+5;
int t[N*4],arr[N],ans[N],f[N];
int n,m,T,k;
vector<pair<pii,int>> q[N];
stack<int> st;

void build(int v, int tl, int tr) {
     if (tl==tr) {
          t[v]=arr[tl];
          return;
     }
     int mid=(tl+tr)/2;
     build(v*2,tl,mid);
     build(v*2+1,mid+1,tr);
     t[v]=max(t[v*2],t[v*2+1]);
}

void update(int v, int tl, int tr, int ind, int val) {
     if (tl==tr) {
          t[v]=val;
          return;
     }
     int mid=(tl+tr)/2;
     if (ind<=mid) update(v*2,tl,mid,ind,val);
     else update(v*2+1,mid+1,tr,ind,val);
     t[v]=max(t[v*2],t[v*2+1]);
}

int query(int v, int tl, int tr, int l, int r) {
     if (tl==l && tr==r) {
          return t[v];
     }
     int mid=(tl+tr)/2;
     if (r<=mid) return query(v*2,tl,mid,l,r);
     if (l>=mid+1) return query(v*2+1,mid+1,tr,l,r);
     return max(query(v*2,tl,mid,l,mid),query(v*2+1,mid+1,tr,mid+1,r));
}

void test_case() {
     cin>>n>>m;

     for (int i=1; i<=n; i++) cin>>arr[i];
     build(1,1,n);

     for (int i=1; i<=m; i++) {
          int l,r,k; cin>>l>>r>>k;
          q[r].pb({{l,k},i});
     }

     for (int i=1; i<=n; i++) {
          while (st.size() && arr[st.top()]<=arr[i]) st.pop();
          if (st.size()) f[i]=st.top();
          st.push(i);
     }

     for (int r=1; r<=n; r++) {
          if (f[r]) update(1,1,n,f[r],arr[f[r]]+arr[r]);
          for (auto a:q[r]) {
               int l=a.f.f,k=a.f.s,i=a.s;
               ans[i]=(query(1,1,n,l,r)<=k);
          }
     }

     for (int i=1; i<=m; i++) cout<<ans[i]<<endl;
}
main () {
	ios :: sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	T=1; 
	while (T--) test_case();
}

Compilation message

sortbooks.cpp:1: warning: ignoring '#pragma gcc diagnostic' [-Wunknown-pragmas]
    1 | #pragma gcc diagnostic "-std=c++1z"
      | 
sortbooks.cpp:79:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   79 | main () {
      | ^~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 31324 KB Output is correct
2 Correct 6 ms 31372 KB Output is correct
3 Incorrect 7 ms 31320 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 31324 KB Output is correct
2 Correct 6 ms 31372 KB Output is correct
3 Incorrect 7 ms 31320 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2137 ms 98588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 173 ms 38968 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 31324 KB Output is correct
2 Correct 6 ms 31372 KB Output is correct
3 Incorrect 7 ms 31320 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 31324 KB Output is correct
2 Correct 6 ms 31372 KB Output is correct
3 Incorrect 7 ms 31320 KB Output isn't correct
4 Halted 0 ms 0 KB -