답안 #677138

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
677138	2023-01-02T11:01:56 Z	Sandarach151	Lasers (NOI19_lasers)	C++17	87 / 100	133 ms	262144 KB

lasers

#include<bits/stdc++.h>
using namespace std;

class RURQ{
	private:
		vector<int> st, lazy;
		int size;
		void propogate(int pos, int l, int r){
			if(lazy[pos]!=-1){
				if(l!=r){
					int temp = (l+r)/2;
					lazy[2*pos+1]=lazy[pos];
					st[2*pos+1]=lazy[2*pos+1]*(temp-l+1);
					lazy[2*pos+2]=lazy[pos];
					st[2*pos+2]=lazy[2*pos+2]*(r-temp);
				}
				lazy[pos]=-1;
			}
		}
		void privupdate(int pos, int l, int r, int ql, int qr, int val){
			if(l>qr || r<ql){
				return;
			}
			else if(ql<=l && r<=qr){
				lazy[pos]=val;
				st[pos]=val*(r-l+1);
			}
			else{
				propogate(pos, l, r);
				int temp = (l+r)/2;
				privupdate(2*pos+1, l, temp, ql, qr, val);
				privupdate(2*pos+2, temp+1, r, ql, qr, val);
				st[pos]=st[2*pos+1]+st[2*pos+2];
			}
		}
		int privgetSum(int pos, int l, int r, int ql, int qr){
			if(l>qr || r<ql){
				return 0;
			}
			else if(ql<=l && r<=qr){
				return st[pos];
			}
			else{
				int temp = (l+r)/2;
				return privgetSum(2*pos+1, l, temp, ql, qr) + privgetSum(2*pos+2, temp+1, r, ql, qr);
			}
		}
	public:
		RURQ(int n) : st(4*n+5, 0), lazy(4*n+5, -1), size(n){}
		void update(int l, int r){
			privupdate(0, 0, size-1, l, r, 1);
		}
		int getSum(int l, int r){
			return privgetSum(0, 0, size-1, l, r);
		}
};


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int l, r;
	cin >> l >> r;
	vector<int> arr[r];
	int summ[r] = {0};
	bool res = true;
	for(int i=0; i<r; i++){
		int x;
		cin >> x;
		for(int j=0; j<x; j++){
			int a;
			cin >> a;
			arr[i].push_back(a);
			summ[i]+=a;
		}
		if(x!=1){
			res=false;
		}
	}
	if(res){
		int ans = 0;
		for(int i=0; i<r; i++){
			ans = max(ans, 2*arr[i][0]-l);
		}
		cout << ans << '\n';
	}
	else{
		RURQ segstree(l);
		for(int i=0; i<r; i++){
			int x = l-summ[i];
			int cur = 0;
			for(long long unsigned int j=0; j<arr[i].size(); j++){
				if(arr[i][j]>x){
					segstree.update(cur+x, cur+arr[i][j]-1);
				}
				cur+=arr[i][j];
			}
		}
		int temp = segstree.getSum(0, l-1);
		cout << temp << '\n';
	}
	return 0;
}

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	320 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	320 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	320 KB	Output is correct

Subtask #2
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	320 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	320 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	320 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	115 ms	34760 KB	Output is correct
13	Correct	1 ms	316 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	97 ms	35184 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	73 ms	29936 KB	Output is correct
2	Correct	24 ms	30036 KB	Output is correct
3	Correct	23 ms	30956 KB	Output is correct
4	Correct	84 ms	31556 KB	Output is correct
5	Correct	46 ms	32320 KB	Output is correct
6	Correct	50 ms	30464 KB	Output is correct
7	Correct	12 ms	25812 KB	Output is correct
8	Correct	50 ms	28736 KB	Output is correct
9	Correct	58 ms	30336 KB	Output is correct
10	Correct	93 ms	30324 KB	Output is correct

Subtask #4
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	320 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	324 KB	Output is correct
5	Correct	1 ms	320 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	328 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct

Subtask #5
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	73 ms	29936 KB	Output is correct
2	Correct	24 ms	30036 KB	Output is correct
3	Correct	23 ms	30956 KB	Output is correct
4	Correct	84 ms	31556 KB	Output is correct
5	Correct	46 ms	32320 KB	Output is correct
6	Correct	50 ms	30464 KB	Output is correct
7	Correct	12 ms	25812 KB	Output is correct
8	Correct	50 ms	28736 KB	Output is correct
9	Correct	58 ms	30336 KB	Output is correct
10	Correct	93 ms	30324 KB	Output is correct
11	Correct	1 ms	320 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	324 KB	Output is correct
15	Correct	1 ms	320 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	328 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	96 ms	33660 KB	Output is correct
22	Correct	64 ms	30340 KB	Output is correct
23	Correct	38 ms	30036 KB	Output is correct
24	Correct	95 ms	31560 KB	Output is correct
25	Correct	113 ms	33628 KB	Output is correct
26	Correct	133 ms	30680 KB	Output is correct
27	Correct	58 ms	30036 KB	Output is correct
28	Correct	86 ms	33528 KB	Output is correct
29	Correct	99 ms	33700 KB	Output is correct
30	Correct	72 ms	30284 KB	Output is correct

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	320 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	320 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	320 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	115 ms	34760 KB	Output is correct
13	Correct	1 ms	316 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	97 ms	35184 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	73 ms	29936 KB	Output is correct
22	Correct	24 ms	30036 KB	Output is correct
23	Correct	23 ms	30956 KB	Output is correct
24	Correct	84 ms	31556 KB	Output is correct
25	Correct	46 ms	32320 KB	Output is correct
26	Correct	50 ms	30464 KB	Output is correct
27	Correct	12 ms	25812 KB	Output is correct
28	Correct	50 ms	28736 KB	Output is correct
29	Correct	58 ms	30336 KB	Output is correct
30	Correct	93 ms	30324 KB	Output is correct
31	Correct	1 ms	320 KB	Output is correct
32	Correct	1 ms	340 KB	Output is correct
33	Correct	1 ms	340 KB	Output is correct
34	Correct	1 ms	324 KB	Output is correct
35	Correct	1 ms	320 KB	Output is correct
36	Correct	1 ms	340 KB	Output is correct
37	Correct	1 ms	340 KB	Output is correct
38	Correct	1 ms	328 KB	Output is correct
39	Correct	1 ms	340 KB	Output is correct
40	Correct	1 ms	340 KB	Output is correct
41	Correct	96 ms	33660 KB	Output is correct
42	Correct	64 ms	30340 KB	Output is correct
43	Correct	38 ms	30036 KB	Output is correct
44	Correct	95 ms	31560 KB	Output is correct
45	Correct	113 ms	33628 KB	Output is correct
46	Correct	133 ms	30680 KB	Output is correct
47	Correct	58 ms	30036 KB	Output is correct
48	Correct	86 ms	33528 KB	Output is correct
49	Correct	99 ms	33700 KB	Output is correct
50	Correct	72 ms	30284 KB	Output is correct
51	Runtime error	113 ms	262144 KB	Execution killed with signal 9
52	Halted	0 ms	0 KB	-

답안 #677138

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 14.0 / 14.0

Subtask #3 20.0 / 20.0

Subtask #4 21.0 / 21.0

Subtask #5 22.0 / 22.0

Subtask #6 0 / 13.0

Subtask #1
10.0 / 10.0

Subtask #2
14.0 / 14.0

Subtask #3
20.0 / 20.0

Subtask #4
21.0 / 21.0

Subtask #5
22.0 / 22.0

Subtask #6
0 / 13.0