Submission #1007708

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007708		makanhulia	Lasers (NOI19_lasers)	C++17	100 / 100	95 ms	11852 KiB

lasers

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lld double
#define int ll
#define usaco(fname) freopen(#fname ".in","r",stdin);freopen(#fname ".out","w",stdout);
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
// const ll INF = 1e18;
const int INF = 1e9;
const int mod = 1e9+7;
const lld PI = acos(-1.0);
int di[] = {1, -1, 0, 0, 1, 1, -1, -1};
int dj[] = {0, 0, 1, -1, 1, -1, 1, -1};
#define debug(x) cout << #x << ": " << x << endl;
#define add(a, b) a += b, a %= mod
#define mul(a, b) ((a % mod) * (b % mod)) % mod
#define all(x) x.begin(),x.end()

void solve() {
  int n,q;cin>>n>>q;

  vector<pair<int, int>> intervals;
  while (q--) {
    int k;cin>>k;
    vector<int> a(k);
    for (int i = 0; i < k; i++) cin >> a[i];

    int sum = accumulate(all(a),0);
    int left = n-sum;

    int now = 0;
    for (int i = 0; i < k; i++) {
      now += a[i];
      intervals.push_back({now-a[i]+left+1, now});
    }
  }

  sort(all(intervals));

  int nowl = -1, nowr = -1;
  int ans = 0;
  // cout << intervals << endl;
  for (int i = 0; i < intervals.size(); i++) {
    auto [l, r] = intervals[i];
    if (l > r) continue;
    if (nowl == -1 && nowr == -1) {
      nowl = l;
      nowr = r;
      continue;
    }
    
    if (l > nowr) {
      ans += nowr-nowl+1;
      nowl = l;
      nowr = r;
    }

    nowr = max(nowr, r);
  }

  if (nowl != -1) ans += nowr-nowl+1;
  cout << ans << endl;
}

int32_t main() {
  ios_base::sync_with_stdio(0);cin.tie(0);
  int t=1;
  while(t--) solve();

  return 0;
}

Compilation message (stderr)

lasers.cpp: In function 'void solve()':
lasers.cpp:44:21: 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]
   44 |   for (int i = 0; i < intervals.size(); 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