Submission #222619

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
222619	2020-04-13T12:44:08 Z	astoria	Fire (JOI20_ho_t5)	C++14	6 / 100	578 ms	24964 KB

ho_t5

#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main(){
	multiset<int> ms;
	int n,q;
	cin>>n>>q;
	int s[n+5];
	for(int i=1; i<=n; i++) cin>>s[i];
	int t[q],l[q],r[q];
	for(int i=0; i<q; i++) cin>>t[i]>>l[i]>>r[i];
	
	int val[n+5];
	val[0] = 0;
	for(int i=1; i<=min(t[0]+1,n); i++){
		ms.insert(s[i]);
		val[i] = *ms.rbegin();
	}
	for(int i=t[0]+2; i<=n; i++){
		ms.insert(s[i]);
		ms.erase(ms.find(s[i-t[0]-1]));
		val[i] = *ms.rbegin();
	}
	int p[n+5]; p[0]=0;
	for(int i=1; i<=n; i++) p[i]=p[i-1]+val[i];
	
	for(int i=0; i<q; i++){
		cout<<(p[r[i]]-p[l[i]-1])<<'\n';
	}
}

Subtask #1

0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	256 KB	Output is correct
2	Incorrect	5 ms	256 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	256 KB	Output is correct
2	Correct	561 ms	18456 KB	Output is correct
3	Correct	522 ms	21228 KB	Output is correct
4	Correct	528 ms	15520 KB	Output is correct
5	Correct	545 ms	23288 KB	Output is correct
6	Correct	496 ms	19168 KB	Output is correct
7	Correct	557 ms	22996 KB	Output is correct
8	Correct	538 ms	20852 KB	Output is correct
9	Correct	543 ms	22752 KB	Output is correct
10	Correct	534 ms	23392 KB	Output is correct
11	Correct	554 ms	24964 KB	Output is correct
12	Correct	578 ms	24432 KB	Output is correct
13	Correct	490 ms	18808 KB	Output is correct
14	Correct	501 ms	22008 KB	Output is correct
15	Correct	506 ms	21976 KB	Output is correct
16	Correct	504 ms	19576 KB	Output is correct

Subtask #3

0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	256 KB	Output is correct
2	Incorrect	476 ms	12924 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #4

0 / 6.0

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

Subtask #5

0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	256 KB	Output is correct
2	Incorrect	5 ms	256 KB	Output isn't correct
3	Halted	0 ms	0 KB	-