oj.uz

Submission #333022

# Submission time Handle Problem Language Result Execution time Memory
333022 2020-12-04T09:14:06 Z guka415 Lasers (NOI19_lasers) C++14
0 / 100
 58 ms 7500 KB 
#define fast ios::sync_with_stdio(false); cin.tie(0)
#define foru(i, k, n) for (int i = k; i < n; i++)
#define ford(i, k, n) for (int i = k; i >= n; i--)
#define pb push_back
#define mp make_pair

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <bitset>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int sz = 5e5+5;
ll l, n;
vector<pair<int, bool>> segs;

inline bool intersect(const pii& lhs, const pii& rhs) {
	return (rhs.first - lhs.second <= 1);
}


int main() {
	fast;
	cin >> l >> n;
	bool bad = 0;
	while (n--) {
		vector<int> v;
		int x, tmp, rsum = 0, lsum = 0;
		cin >> x;
		foru(i, 0, x) {
			cin >> tmp;
			rsum += tmp;
			v.pb(tmp);
		}
		if (rsum == l) {
			bad = 1;
			continue;
		}
		vector<pii> yes;
		yes.pb({ 0,l - rsum - 1 });
		lsum += v[0];
		rsum -= v[0];
		foru(i, 1, x + 1) {
			pii inval = { lsum, l - rsum - 1 }, yb = yes.back();
			if (intersect(yb, inval)) {
				yes.back() = { yb.first,inval.second };
			}
			else {
				yes.pb(inval);
			}
			if (i != x) {
				lsum += v[i];
				rsum -= v[i];
			}
		}
		foru(i, 0, yes.size() - 1) {
			segs.pb({ yes[i].second + 1,0 });
			segs.pb({ yes[i + 1].first - 1,1 });
		}
	}
	sort(segs.begin(), segs.end());
	ll tot = 0, prvLit = -1;
	int o = 0;
	for (auto x : segs) {
		if (!x.second) {
			if (o == 0) {
				prvLit = x.first;
			}
			o++;
		}
		else {
			o--;
			if (o == 0) {
				tot += (x.first - prvLit + 1);
			}
		}
	}
	cout << tot << '\n';
	return 0;
}

Compilation message

lasers.cpp: In function 'int main()':
lasers.cpp:2:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define foru(i, k, n) for (int i = k; i < n; i++)
......
   62 |   foru(i, 0, yes.size() - 1) {
      |        ~~~~~~~~~~~~~~~~~~~~              
lasers.cpp:62:3: note: in expansion of macro 'foru'
   62 |   foru(i, 0, yes.size() - 1) {
      |   ^~~~
lasers.cpp:31:7: warning: variable 'bad' set but not used [-Wunused-but-set-variable]
   31 |  bool bad = 0;
      |       ^~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 7500 KB Output is correct
2 Incorrect 8 ms 1668 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

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

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 7500 KB Output is correct
2 Incorrect 8 ms 1668 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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