oj.uz

답안 #505869

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
505869 2022-01-11T09:09:20 Z lukameladze Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
0 / 100
 185 ms 6356 KB 
# 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]<<" ";
    }
}

Compilation message

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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 288 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 284 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Incorrect 1 ms 332 KB Output isn't correct

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 288 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 284 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Incorrect 1 ms 332 KB Output isn't correct

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 112 ms 3780 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 185 ms 6356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 288 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 284 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Incorrect 1 ms 332 KB Output isn't correct

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 288 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 284 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Incorrect 1 ms 332 KB Output isn't correct