제출 #899134

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
899134		Nika533	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	2133 ms	98932 KiB

sortbooks

#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();
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23