제출 #505869

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
505869		lukameladze	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	185 ms	6356 KiB

sortbooks

# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pii pair <int, int>
using namespace std;
const int N = 3e5 + 5;
stack<int> st;
int n,q,a[N],le[N],ri[N],x[N];
vector <pii> v;
int tree[4*N],l,r,xx,curle,ans[N];
void update(int node, int le, int ri , int idx, int val) {
     if (le>idx || ri<idx) return ;
     if (le==ri) {
          tree[node]=max(tree[node],val);
          return;
     }
     int mid=(le+ri)/2;
     update(2*node , le, mid, idx, val);
     update(2*node+1, mid+1, ri, idx,val);
     tree[node]=max(tree[2*node], tree[2*node+1]);
}
int getans(int node, int le, int ri , int start, int end) {
     if (le>end || ri<start) return 0;
     if (le>=start && ri<=end) {
          return tree[node];
     }
     int mid=(le+ri)/2;
     return max(getans(2*node, le, mid ,start, end), getans(2*node+1, mid+1, ri , start, end));
}
/*void update(int node,int le,int ri,int start,int end,int val) {
	if(lazy[node]) {
		tree[node] = max(tree[node],lazy[node]);
		if(le!=ri) {
			lazy[2*node] = max(lazy[2*node],lazy[node]);
			lazy[2*node+1]  = max(lazy[2*node + 1], lazy[node]);
		}
		lazy[node] = 0;
	}
	if(le>end || ri<start) 
	return;
	if(start<=le && ri<=end) {
		tree[node] = max(tree[node],val);
		if(le!=ri) {
			lazy[2*node] = max(lazy[2*node],val);
			lazy[2*node+1]  = max(lazy[2*node + 1], val);
		}
		return;
	}
	int mid=(le+ri)/2;
	update(2*node,le,mid,start,end,val);
	update(2*node+1,mid+1,ri,start,end,val);
	tree[node]=max(tree[2*node],tree[2*node+1]);
}
int getans(int node,int le,int ri,int start,int end) {
	if(lazy[node]) {
		tree[node] = max(tree[node],lazy[node]);
		if(le!=ri) {
			lazy[2*node] = max(lazy[2*node],lazy[node]);
			lazy[2*node+1]  = max(lazy[2*node + 1], lazy[node]);
		}
		lazy[node] = 0;
	}
	if(le>end || ri<start) return 0;
	if(start<=le && ri<=end) {
		return tree[node];
	}
	int mid=(le+ri)/2;
	return max(getans(2*node,le,mid,start,end), getans(2*node+1,mid+1,ri,start,end));
}*/
void add(int idx) {
    int num = a[idx];
    while(st.size() && a[st.top()] <= num) {
        int x = st.top();
       // cout<<x<<" "<<num + a[st.top()]<<endl;
        update(1,1,n,x,num + a[st.top()]);
        st.pop();
    }
    st.push(idx);
}
main() {
    cin>>n>>q;
    for (int i = 1; i <= n ;i++) {
        cin>>a[i];
    }
    for (int i = 1; i <= q; i++) {
        cin>>le[i]>>ri[i]>>x[i];
        v.pb({le[i],i});
    }
    //build(1,1,n);
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    curle = n;
    for (int i = 0; i < v.size(); i++) {
        l = le[v[i].s];
        r = ri[v[i].s]; 
        xx = x[v[i].s]; 
        while (curle >= l) {
            add(curle);
            curle--;
        }
        ans[v[i].s] = (getans(1,1,n,l,r) <= xx);//cout<<endl;
    }
    for (int i = 1; i <= q; i++) {
        cout<<ans[i]<<" ";
    }
}

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

sortbooks.cpp:81:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   81 | main() {
      | ^~~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:94:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23