Submission #676481

#	Time	Username	Problem	Language	Result	Execution time	Memory
676481		penguin133	Lasers (NOI19_lasers)	C++17	100 / 100	458 ms	21392 KiB

lasers

#include <bits/stdc++.h>
using namespace std;
#define int long long
int X[500005], P[500005],S[500005];
map<int, int>m;

main(){
	int n,r;
	cin >> n >> r;
	int maxi = 0;
	while(r--){
		int a;
		cin >> a;
		maxi = max(maxi, a);
		vector<pair<int, int> >v;
		for(int i=1;i<=maxi;i++)X[i] = 0;
		for(int i=1;i<=a;i++){
			cin >> X[i];
			P[i] = P[i-1] + X[i];
		}
		int b = n;
		for(int i=a+1;i>=1;i--){
			b -= X[i];
			v.push_back(make_pair(P[i-1] + 1, b));
		}
		sort(v.begin(), v.end());
		for(int i=0;i<v.size()-1;i++){
			if(v[i].second + 1 < v[i+1].first)m[v[i].second+1]=max(m[v[i].second + 1], v[i+1].first-1);
		}
	}
	map<int, int> :: iterator it;
	it = m.begin();
	int cnt = 0;
	while(it != m.end()){
		int c = it->second, d = it->first;
		it++;
		while(it != m.end() && c >= it->first){
			c = max(c, it->second);
			it++;
		}
		cnt += (c-d)+1;
	}
	cout << cnt;
}

Compilation message (stderr)

lasers.cpp:7:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    7 | main(){
      | ^~~~
lasers.cpp: In function 'int main()':
lasers.cpp:27:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   for(int i=0;i<v.size()-1;i++){
      |               ~^~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 21 / 21
• Subtask 5: 22 / 22
• Subtask 6: 13 / 13