Submission #393551

#	Time	Username	Problem	Language	Result	Execution time	Memory
393551		ADMathNoob	Inspector (POI13_ins)	C++11	0 / 100	1753 ms	36060 KiB

ins

/*
 * author:  ADMathNoob
 * created: 04/22/21 14:39:48
 * problem: https://www.acmicpc.net/problem/8242
 */

/*
g++ boj_8242.cpp -D_DEBUG -std=c++11 -Wl,--stack=268435456 -Wall -Wfatal-errors -ggdb && gdb a
g++ boj_8242.cpp -D_DEBUG -std=c++11 -Wl,--stack=268435456 -O3 -Wall -Wfatal-errors

Try to avoid O(n log^2(n)) per case?

pessimistic
*/

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n, m;
    cin >> n >> m;
    vector<int> when(m);
    vector<int> who(m);
    vector<int> others(m);
    for (int j = 0; j < m; j++) {
      cin >> when[j] >> who[j] >> others[j];
      --when[j];
      --who[j];
    }
    int low = 0, high = m;
    while (low < high) {
      int mid = (low + high + 1) >> 1;
      vector<int> cnt(m, -1);
      bool ok = true;
      vector<int> first(n, m);
      vector<int> last(n, -1);
      // check that the claims are consistent for each point in time
      for (int j = 0; j < mid; j++) {
        int t = when[j];
        if (cnt[t] != -1 && cnt[t] != others[j] + 1) {
          ok = false;
        }
        cnt[t] = others[j] + 1;
        first[who[j]] = min(first[who[j]], t);
        last[who[j]] = max(last[who[j]], t);
        // assert(0 <= first[who[j]] && first[who[j]] <= last[who[j]] && last[who[j]] < m);
      }  // OK
      if (!ok) {
        high = mid - 1;
        continue;
      }
      // cerr << "first " << mid << ": at first glance, consistent\n";

      {
        // check that there aren't times with too many people already
        vector<int> a(m + 1, 0);
        for (int i = 0; i < n; i++) {
          if (first[i] != m) {
            a[first[i]] += 1;
            a[last[i] + 1] -= 1;
          }
        }
        for (int t = 0; t < m; t++) {
          if (cnt[t] != -1 && a[t] > cnt[t]) {
            // cerr << "too many people at time " << t << '\n';
            ok = false;
          }
          a[t + 1] += a[t];
        }
        assert(a[m] == 0);
        if (!ok) {
          high = mid - 1;
          continue;
        }
      }  // OK

      vector<int> add(m, 0);
      vector<int> remove(m, 0);
      for (int i = 0; i < n; i++) {
        if (first[i] != m) {
          add[first[i]] += 1;
          remove[last[i]] += 1;
        }
      }
      {
        // extend intervals right
        vector<int> new_remove(m, 0);
        int in = 0;  // in the office
        for (int t = 0; t < m; t++) {
          in += add[t];
          if (cnt[t] != -1) {
            if (in > cnt[t]) {
              int drop = in - cnt[t];
              // cerr << "too many at time " << t << "; removing " << drop << "\n";
              assert(t > 0);
              new_remove[t - 1] = drop;
              in -= drop;
            }
          }
        }
        new_remove[m - 1] = in;
        remove = new_remove;
        assert(accumulate(add.begin(), add.end(), 0) == accumulate(remove.begin(), remove.end(), 0));
      }  // OK
      {
        // extend intervals left
        vector<int> new_add(m, 0);
        int in = 0;
        for (int t = m - 1; t >= 0; t--) {
          in += remove[t];
          if (cnt[t] != -1) {
            if (in > cnt[t]) {
              int drop = in - cnt[t];
              assert(t < m - 1);
              new_add[t + 1] = drop;
              in -= drop;
            }
          }
        }
        new_add[0] = in;
        add = new_add;
        assert(accumulate(add.begin(), add.end(), 0) == accumulate(remove.begin(), remove.end(), 0));
      }  // OK

      {
        // check that there aren't times with too many people again
        vector<int> a(m + 1, 0);
        for (int i = 0; i < n; i++) {
          if (first[i] != m) {
            a[first[i]] += 1;
            a[last[i] + 1] -= 1;
          }
        }
        for (int t = 0; t < m; t++) {
          assert(cnt[t] == -1 || a[t] <= cnt[t]);
          a[t + 1] += a[t];
        }
      }

      // cerr << "add remove\n";
      // for (int i = 0; i < m; i++) {
      //   cerr << add[i] << ' ' << remove[i] << '\n';
      // }
      // cerr << '\n';

      int in = 0;
      // cerr << unused << " people unaccounted for\n";
      int needed = 0;
      for (int t = 0; t < m; t++) {
        in += add[t];
        if (cnt[t] != -1) {
          if (in < cnt[t]) {
            needed += cnt[t] - in;
          }
          in = cnt[t];
        }
        in -= remove[t];
        // assert(in >= 0);
      }
      int extras = count(first.begin(), first.end(), m);
      if (needed > extras) {
        ok = false;
      }
      if (ok) {
        low = mid;
      } else {
        high = mid - 1;
      }
    }
    cout << low << '\n';
  }
  return 0;
}

• Subtask 1: 0 / 100