답안 #166421

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
166421	2019-12-02T10:28:30 Z	GioChkhaidze	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	47 / 100	2311 ms	129204 KB

sortbooks

#include <bits/stdc++.h>
#define Tree int h,int l,int r
#define Left (h<<1),l,((l+r)>>1)
#define Right ((h<<1)|1),((l+r)>>1)+1,r
using namespace std;
const int N=2e6+1;
bool ANS[N];
int n,q,idx,val,L,R;
int w[N],a[N],b[N],c[N],Greater[N],v[4*N];
stack < int > st;
vector < int > Query[N];
void Upd(Tree) { 
	if (idx<l || r<idx) return;
	if (l==idx && r==idx)  { v[h]=val; return; }
	Upd(Left),Upd(Right);
	if (v[(h<<1)]>v[((h<<1)|1)]) v[h]=v[(h<<1)];	
							else v[h]=v[((h<<1)|1)];
}

int Get(Tree) { 
	if (r<L || R<l) return 0;
	if (L<=l && r<=R) return v[h];
	int x=Get(Left),y=Get(Right);
	if (x<y) return y;
	return x;
}

main () {
	scanf("%d%d",&n,&q);
	
	for (int i=1; i<=n; i++) 
		scanf("%d",&w[i]);
	
	w[0]=1e9;
	st.push(0);
	
	for (int i=1; i<=n; i++) {
		while (st.size() && w[st.top()]<=w[i]) st.pop();
		Greater[i]=st.top();	
		st.push(i);
	}
	
	for (int i=1; i<=q; i++) {
		scanf("%d%d%d",&a[i],&b[i],&c[i]);
		Query[b[i]].push_back(i);
	}
	
	for (int i=1; i<=n; i++) {
		if (Greater[i]) {
			idx=Greater[i],val=w[idx]+w[i];
			Upd(1,1,n);
		}
		
		for (int j=0; j<Query[i].size(); j++) {
			idx=Query[i][j],R=i,L=a[idx];
			if (Get(1,1,n)<=c[idx]) ANS[idx]=1;	
						  else ANS[idx]=0;
		}	
	}
	
	for (int i=1; i<=q; i++) 
		printf("%d\n",ANS[i]);
}

Compilation message

sortbooks.cpp:28:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:54:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0; j<Query[i].size(); j++) {
                 ~^~~~~~~~~~~~~~~~
sortbooks.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&q);
  ~~~~~^~~~~~~~~~~~~~
sortbooks.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&w[i]);
   ~~~~~^~~~~~~~~~~~
sortbooks.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&a[i],&b[i],&c[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	46 ms	47480 KB	Output is correct
2	Correct	45 ms	47352 KB	Output is correct
3	Correct	46 ms	47352 KB	Output is correct
4	Correct	46 ms	47352 KB	Output is correct
5	Correct	106 ms	47352 KB	Output is correct
6	Correct	46 ms	47352 KB	Output is correct
7	Correct	46 ms	47352 KB	Output is correct
8	Correct	46 ms	47340 KB	Output is correct
9	Correct	47 ms	47480 KB	Output is correct
10	Correct	46 ms	47352 KB	Output is correct

Subtask #2
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	46 ms	47480 KB	Output is correct
2	Correct	45 ms	47352 KB	Output is correct
3	Correct	46 ms	47352 KB	Output is correct
4	Correct	46 ms	47352 KB	Output is correct
5	Correct	106 ms	47352 KB	Output is correct
6	Correct	46 ms	47352 KB	Output is correct
7	Correct	46 ms	47352 KB	Output is correct
8	Correct	46 ms	47340 KB	Output is correct
9	Correct	47 ms	47480 KB	Output is correct
10	Correct	46 ms	47352 KB	Output is correct
11	Correct	50 ms	47504 KB	Output is correct
12	Correct	51 ms	47680 KB	Output is correct
13	Correct	66 ms	47696 KB	Output is correct
14	Correct	58 ms	47708 KB	Output is correct
15	Correct	52 ms	47736 KB	Output is correct
16	Correct	51 ms	47736 KB	Output is correct
17	Correct	50 ms	47612 KB	Output is correct
18	Correct	63 ms	47584 KB	Output is correct

Subtask #3
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2264 ms	117332 KB	Output is correct
2	Correct	2233 ms	129204 KB	Output is correct
3	Correct	2230 ms	129004 KB	Output is correct
4	Correct	2311 ms	128320 KB	Output is correct
5	Correct	1797 ms	119564 KB	Output is correct

Subtask #4
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	202 ms	54148 KB	Output is correct
2	Correct	176 ms	53496 KB	Output is correct
3	Correct	165 ms	53072 KB	Output is correct
4	Correct	185 ms	53112 KB	Output is correct
5	Correct	169 ms	53236 KB	Output is correct
6	Correct	139 ms	52000 KB	Output is correct
7	Correct	135 ms	52088 KB	Output is correct
8	Correct	158 ms	52824 KB	Output is correct
9	Correct	98 ms	50676 KB	Output is correct
10	Correct	152 ms	52824 KB	Output is correct

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	46 ms	47480 KB	Output is correct
2	Correct	45 ms	47352 KB	Output is correct
3	Correct	46 ms	47352 KB	Output is correct
4	Correct	46 ms	47352 KB	Output is correct
5	Correct	106 ms	47352 KB	Output is correct
6	Correct	46 ms	47352 KB	Output is correct
7	Correct	46 ms	47352 KB	Output is correct
8	Correct	46 ms	47340 KB	Output is correct
9	Correct	47 ms	47480 KB	Output is correct
10	Correct	46 ms	47352 KB	Output is correct
11	Correct	50 ms	47504 KB	Output is correct
12	Correct	51 ms	47680 KB	Output is correct
13	Correct	66 ms	47696 KB	Output is correct
14	Correct	58 ms	47708 KB	Output is correct
15	Correct	52 ms	47736 KB	Output is correct
16	Correct	51 ms	47736 KB	Output is correct
17	Correct	50 ms	47612 KB	Output is correct
18	Correct	63 ms	47584 KB	Output is correct
19	Correct	412 ms	63752 KB	Output is correct
20	Correct	415 ms	63904 KB	Output is correct
21	Correct	339 ms	61968 KB	Output is correct
22	Correct	346 ms	61976 KB	Output is correct
23	Correct	344 ms	61944 KB	Output is correct
24	Runtime error	159 ms	100964 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
25	Halted	0 ms	0 KB	-

Subtask #6
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	46 ms	47480 KB	Output is correct
2	Correct	45 ms	47352 KB	Output is correct
3	Correct	46 ms	47352 KB	Output is correct
4	Correct	46 ms	47352 KB	Output is correct
5	Correct	106 ms	47352 KB	Output is correct
6	Correct	46 ms	47352 KB	Output is correct
7	Correct	46 ms	47352 KB	Output is correct
8	Correct	46 ms	47340 KB	Output is correct
9	Correct	47 ms	47480 KB	Output is correct
10	Correct	46 ms	47352 KB	Output is correct
11	Correct	50 ms	47504 KB	Output is correct
12	Correct	51 ms	47680 KB	Output is correct
13	Correct	66 ms	47696 KB	Output is correct
14	Correct	58 ms	47708 KB	Output is correct
15	Correct	52 ms	47736 KB	Output is correct
16	Correct	51 ms	47736 KB	Output is correct
17	Correct	50 ms	47612 KB	Output is correct
18	Correct	63 ms	47584 KB	Output is correct
19	Correct	2264 ms	117332 KB	Output is correct
20	Correct	2233 ms	129204 KB	Output is correct
21	Correct	2230 ms	129004 KB	Output is correct
22	Correct	2311 ms	128320 KB	Output is correct
23	Correct	1797 ms	119564 KB	Output is correct
24	Correct	202 ms	54148 KB	Output is correct
25	Correct	176 ms	53496 KB	Output is correct
26	Correct	165 ms	53072 KB	Output is correct
27	Correct	185 ms	53112 KB	Output is correct
28	Correct	169 ms	53236 KB	Output is correct
29	Correct	139 ms	52000 KB	Output is correct
30	Correct	135 ms	52088 KB	Output is correct
31	Correct	158 ms	52824 KB	Output is correct
32	Correct	98 ms	50676 KB	Output is correct
33	Correct	152 ms	52824 KB	Output is correct
34	Correct	412 ms	63752 KB	Output is correct
35	Correct	415 ms	63904 KB	Output is correct
36	Correct	339 ms	61968 KB	Output is correct
37	Correct	346 ms	61976 KB	Output is correct
38	Correct	344 ms	61944 KB	Output is correct
39	Runtime error	159 ms	100964 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
40	Halted	0 ms	0 KB	-

답안 #166421

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 9.0 / 9.0

Subtask #3 13.0 / 13.0

Subtask #4 17.0 / 17.0

Subtask #5 0 / 30.0

Subtask #6 0 / 23.0

Subtask #1
8.0 / 8.0

Subtask #2
9.0 / 9.0

Subtask #3
13.0 / 13.0

Subtask #4
17.0 / 17.0

Subtask #5
0 / 30.0

Subtask #6
0 / 23.0