Submission #393551

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
393551	2021-04-24T01:46:03 Z	ADMathNoob	Inspector (POI13_ins)	C++11	0 / 100	1753 ms	36060 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	204 KB	Output isn't correct
2	Incorrect	1 ms	336 KB	Output isn't correct
3	Incorrect	1 ms	332 KB	Output isn't correct
4	Incorrect	3 ms	332 KB	Output isn't correct
5	Incorrect	6 ms	328 KB	Output isn't correct
6	Incorrect	11 ms	564 KB	Output isn't correct
7	Incorrect	22 ms	748 KB	Output isn't correct
8	Incorrect	124 ms	3312 KB	Output isn't correct
9	Incorrect	285 ms	6544 KB	Output isn't correct
10	Incorrect	589 ms	13156 KB	Output isn't correct
11	Incorrect	827 ms	17512 KB	Output isn't correct
12	Incorrect	1753 ms	36060 KB	Output isn't correct
13	Incorrect	1518 ms	34700 KB	Output isn't correct