oj.uz

Submission #146920

# Submission time Handle Problem Language Result Execution time Memory
146920 2019-08-26T15:33:30 Z Pajaraja Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 2784 ms 175736 KB 
#include <bits/stdc++.h>
#define MAXN 1000007
using namespace std;
int seg[4*MAXN],a[MAXN],ans[MAXN];
vector<int> ul[MAXN],uk[MAXN],ind[MAXN];
void upd(int l,int r,int x,int v,int ind)
{
	if(l==r) {seg[ind]=v; return;}
	int s=(l+r)/2;
	if(x<=s) upd(l,s,x,v,2*ind);
	else upd(s+1,r,x,v,2*ind+1);
	seg[ind]=max(seg[2*ind],seg[2*ind+1]);
}
int nmax(int l,int r,int lt,int rt,int ind)
{
	if(l>=lt && r<=rt) return seg[ind];
	if(l>rt || r<lt) return 0;
	int s=(l+r)/2;
	return max(nmax(l,s,lt,rt,2*ind),nmax(s+1,r,lt,rt,2*ind+1));
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	a[0]=1000000000;
	for(int i=0;i<m;i++)
	{
		int t1,t2,t3;
		scanf("%d%d%d",&t1,&t2,&t3);
		ul[t2].push_back(t1); uk[t2].push_back(t3); ind[t2].push_back(i);
	}
	stack<int> st; st.push(0);
	for(int i=1;i<=n;i++)
	{
		while(a[st.top()]<a[i]) st.pop();
		upd(0,n,st.top(),a[i]+a[st.top()],1);
		st.push(i);
		for(int j=0;j<ul[i].size();j++) ans[ind[i][j]]=(nmax(0,n,ul[i][j],i,1)>uk[i][j]?0:1);
	}
	for(int i=0;i<m;i++) printf("%d\n",ans[i]);
}

Compilation message

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:39:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<ul[i].size();j++) ans[ind[i][j]]=(nmax(0,n,ul[i][j],i,1)>uk[i][j]?0:1);
               ~^~~~~~~~~~~~~
sortbooks.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
sortbooks.cpp:25:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%d",&a[i]);
                        ~~~~~^~~~~~~~~~~~
sortbooks.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&t1,&t2,&t3);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 70780 KB Output is correct
2 Correct 82 ms 70836 KB Output is correct
3 Correct 68 ms 70776 KB Output is correct
4 Correct 68 ms 70780 KB Output is correct
5 Correct 67 ms 70756 KB Output is correct
6 Correct 69 ms 70932 KB Output is correct
7 Correct 68 ms 70776 KB Output is correct
8 Correct 68 ms 70904 KB Output is correct
9 Correct 74 ms 70808 KB Output is correct
10 Incorrect 69 ms 70776 KB Output isn't correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 70780 KB Output is correct
2 Correct 82 ms 70836 KB Output is correct
3 Correct 68 ms 70776 KB Output is correct
4 Correct 68 ms 70780 KB Output is correct
5 Correct 67 ms 70756 KB Output is correct
6 Correct 69 ms 70932 KB Output is correct
7 Correct 68 ms 70776 KB Output is correct
8 Correct 68 ms 70904 KB Output is correct
9 Correct 74 ms 70808 KB Output is correct
10 Incorrect 69 ms 70776 KB Output isn't correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2689 ms 174604 KB Output is correct
2 Correct 2784 ms 175608 KB Output is correct
3 Correct 2657 ms 175476 KB Output is correct
4 Correct 2706 ms 175568 KB Output is correct
5 Incorrect 2593 ms 175736 KB Output isn't correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 70780 KB Output is correct
2 Correct 82 ms 70836 KB Output is correct
3 Correct 68 ms 70776 KB Output is correct
4 Correct 68 ms 70780 KB Output is correct
5 Correct 67 ms 70756 KB Output is correct
6 Correct 69 ms 70932 KB Output is correct
7 Correct 68 ms 70776 KB Output is correct
8 Correct 68 ms 70904 KB Output is correct
9 Correct 74 ms 70808 KB Output is correct
10 Incorrect 69 ms 70776 KB Output isn't correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 70780 KB Output is correct
2 Correct 82 ms 70836 KB Output is correct
3 Correct 68 ms 70776 KB Output is correct
4 Correct 68 ms 70780 KB Output is correct
5 Correct 67 ms 70756 KB Output is correct
6 Correct 69 ms 70932 KB Output is correct
7 Correct 68 ms 70776 KB Output is correct
8 Correct 68 ms 70904 KB Output is correct
9 Correct 74 ms 70808 KB Output is correct
10 Incorrect 69 ms 70776 KB Output isn't correct