oj.uz

Submission #146921

# Submission time Handle Problem Language Result Execution time Memory
146921 2019-08-26T15:35:03 Z Pajaraja Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
47 / 100
 2706 ms 160760 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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 70904 KB Output is correct
2 Correct 69 ms 70776 KB Output is correct
3 Correct 68 ms 70776 KB Output is correct
4 Correct 68 ms 70776 KB Output is correct
5 Correct 68 ms 70776 KB Output is correct
6 Correct 68 ms 70904 KB Output is correct
7 Correct 68 ms 70904 KB Output is correct
8 Correct 69 ms 70952 KB Output is correct
9 Correct 67 ms 70776 KB Output is correct
10 Correct 69 ms 70812 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 70904 KB Output is correct
2 Correct 69 ms 70776 KB Output is correct
3 Correct 68 ms 70776 KB Output is correct
4 Correct 68 ms 70776 KB Output is correct
5 Correct 68 ms 70776 KB Output is correct
6 Correct 68 ms 70904 KB Output is correct
7 Correct 68 ms 70904 KB Output is correct
8 Correct 69 ms 70952 KB Output is correct
9 Correct 67 ms 70776 KB Output is correct
10 Correct 69 ms 70812 KB Output is correct
11 Correct 72 ms 71032 KB Output is correct
12 Correct 74 ms 71148 KB Output is correct
13 Correct 73 ms 71288 KB Output is correct
14 Correct 78 ms 71372 KB Output is correct
15 Correct 76 ms 71288 KB Output is correct
16 Correct 74 ms 71288 KB Output is correct
17 Correct 73 ms 71288 KB Output is correct
18 Correct 73 ms 71160 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2642 ms 142964 KB Output is correct
2 Correct 2706 ms 142716 KB Output is correct
3 Correct 2666 ms 142916 KB Output is correct
4 Correct 2659 ms 142840 KB Output is correct
5 Correct 2468 ms 134672 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 77664 KB Output is correct
2 Correct 209 ms 77560 KB Output is correct
3 Correct 230 ms 77944 KB Output is correct
4 Correct 245 ms 78432 KB Output is correct
5 Correct 250 ms 78740 KB Output is correct
6 Correct 167 ms 75384 KB Output is correct
7 Correct 188 ms 75336 KB Output is correct
8 Correct 213 ms 78188 KB Output is correct
9 Correct 125 ms 74188 KB Output is correct
10 Correct 215 ms 78044 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 70904 KB Output is correct
2 Correct 69 ms 70776 KB Output is correct
3 Correct 68 ms 70776 KB Output is correct
4 Correct 68 ms 70776 KB Output is correct
5 Correct 68 ms 70776 KB Output is correct
6 Correct 68 ms 70904 KB Output is correct
7 Correct 68 ms 70904 KB Output is correct
8 Correct 69 ms 70952 KB Output is correct
9 Correct 67 ms 70776 KB Output is correct
10 Correct 69 ms 70812 KB Output is correct
11 Correct 72 ms 71032 KB Output is correct
12 Correct 74 ms 71148 KB Output is correct
13 Correct 73 ms 71288 KB Output is correct
14 Correct 78 ms 71372 KB Output is correct
15 Correct 76 ms 71288 KB Output is correct
16 Correct 74 ms 71288 KB Output is correct
17 Correct 73 ms 71288 KB Output is correct
18 Correct 73 ms 71160 KB Output is correct
19 Correct 510 ms 91128 KB Output is correct
20 Correct 509 ms 91256 KB Output is correct
21 Correct 380 ms 85856 KB Output is correct
22 Correct 390 ms 85880 KB Output is correct
23 Correct 389 ms 85904 KB Output is correct
24 Runtime error 421 ms 160760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 70904 KB Output is correct
2 Correct 69 ms 70776 KB Output is correct
3 Correct 68 ms 70776 KB Output is correct
4 Correct 68 ms 70776 KB Output is correct
5 Correct 68 ms 70776 KB Output is correct
6 Correct 68 ms 70904 KB Output is correct
7 Correct 68 ms 70904 KB Output is correct
8 Correct 69 ms 70952 KB Output is correct
9 Correct 67 ms 70776 KB Output is correct
10 Correct 69 ms 70812 KB Output is correct
11 Correct 72 ms 71032 KB Output is correct
12 Correct 74 ms 71148 KB Output is correct
13 Correct 73 ms 71288 KB Output is correct
14 Correct 78 ms 71372 KB Output is correct
15 Correct 76 ms 71288 KB Output is correct
16 Correct 74 ms 71288 KB Output is correct
17 Correct 73 ms 71288 KB Output is correct
18 Correct 73 ms 71160 KB Output is correct
19 Correct 2642 ms 142964 KB Output is correct
20 Correct 2706 ms 142716 KB Output is correct
21 Correct 2666 ms 142916 KB Output is correct
22 Correct 2659 ms 142840 KB Output is correct
23 Correct 2468 ms 134672 KB Output is correct
24 Correct 257 ms 77664 KB Output is correct
25 Correct 209 ms 77560 KB Output is correct
26 Correct 230 ms 77944 KB Output is correct
27 Correct 245 ms 78432 KB Output is correct
28 Correct 250 ms 78740 KB Output is correct
29 Correct 167 ms 75384 KB Output is correct
30 Correct 188 ms 75336 KB Output is correct
31 Correct 213 ms 78188 KB Output is correct
32 Correct 125 ms 74188 KB Output is correct
33 Correct 215 ms 78044 KB Output is correct
34 Correct 510 ms 91128 KB Output is correct
35 Correct 509 ms 91256 KB Output is correct
36 Correct 380 ms 85856 KB Output is correct
37 Correct 390 ms 85880 KB Output is correct
38 Correct 389 ms 85904 KB Output is correct
39 Runtime error 421 ms 160760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -