Submission #677138

#	Time	Username	Problem	Language	Result	Execution time	Memory
677138		Sandarach151	Lasers (NOI19_lasers)	C++17	87 / 100	133 ms	262144 KiB

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 / 10
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 21 / 21
• Subtask 5: 22 / 22
• Subtask 6: 0 / 13