Submission #230156

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
230156	2020-05-08T18:24:46 Z	xiaowuc1	Inspector (POI13_ins)	C++14	92 / 100	5000 ms	6628 KB

ins

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <complex>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_set>
#include <vector>

using namespace std;

// BEGIN NO SAD
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define derr if(1) cerr
typedef vector<int> vi;
// END NO SAD

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<ll>> matrix;

typedef pair<int, pii> state;

struct statement {
  int t, person, work, orig;
  bool operator<(statement& s) {
    return t < s.t;
  }
};

int n, m;
statement l[100005];

int earliest[100005];
int latest[100005];
bool can(int thresh) {
  memset(earliest, 1, sizeof(earliest));
  memset(latest, -1, sizeof(latest));
  int lastt = -1;
  int lastclaim = -1;
  // first check that everyone claims the same number of people
  for(int i = 0; i < m; i++) {
    if(l[i].orig >= thresh) continue;
    if(l[i].work > n) return false;
    if(l[i].t == lastt && l[i].work != lastclaim) return false;
    lastt = l[i].t;
    lastclaim = l[i].work;
    earliest[l[i].person] = min(earliest[l[i].person], i);
    latest[l[i].person] = i;
  }
  set<int> working; // working
  set<pii> preworking;
  int postworking = 0; // working
  int flexible = 0;
  set<pii> preempt; // working
  for(int i = 1; i <= n; i++) {
    if(earliest[i] <= 1e6) preworking.insert({earliest[i], i});
    else flexible++;
  }
  for(int i = 0; i < m;) {
    if(l[i].orig >= thresh) {
      i++;
      continue;
    }
    int j = i;
    while(j < m && l[i].t == l[j].t) j++;
    for(int k = i; k < j; k++) {
      if(l[k].orig >= thresh) continue;
      // if it is their first statement, they must start working now
      if(earliest[l[k].person] == k) {
        int amt = preworking.erase({earliest[l[k].person], l[k].person});
        amt += preempt.erase({earliest[l[k].person], l[k].person});
        assert(amt == 1);
        working.insert(l[k].person);
      }
    }
    while(sz(working) + postworking + sz(preempt) < l[i].work) {
      if(sz(preworking)) {
        preempt.insert(*preworking.begin());
        preworking.erase(preworking.begin());
      }
      else if(flexible) {
        postworking++;
        flexible--;
      }
      else {
        return false;
      }
    }
    while(sz(working) + postworking + sz(preempt) > l[i].work) {
      if(postworking > 0) {
        postworking--;
      }
      else if(sz(preempt) && flexible) {
        preworking.insert(*preempt.begin());
        preempt.erase(preempt.begin());
        flexible--;
      }
      else {
        return false;
      }
    }
    for(int k = i; k < j; k++) {
      if(l[k].orig >= thresh) continue;
      // if it is their last statement, they are post-working now
      if(latest[l[k].person] == k) {
        assert(working.count(l[k].person));
        working.erase(l[k].person);
        postworking++;
      }
    }
    i = j;
  }
  return true;
}

void rsolve() {
  cin >> n >> m;
  for(int i = 0; i < m; i++) {
    l[i].orig = i;
    cin >> l[i].t >> l[i].person >> l[i].work;
    l[i].work++;
  }
  sort(l, l+m);
  int lhs = 0;
  int rhs = m;
  while(lhs < rhs) {
    int mid = (lhs+rhs+1)/2;
    if(can(mid)) lhs = mid;
    else rhs = mid - 1;
  }
  cout << lhs << "\n";
}

void solve() {
  int t;
  cin >> t;
  while(t--) rsolve();
}
// are there edge cases (N=1?)
// are array sizes proper (scaled by proper constant, for example 2* for koosaga tree)
// integer overflow?
// DS reset properly between test cases

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
}

Subtask #1

92.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	1152 KB	Output is correct
2	Correct	11 ms	1152 KB	Output is correct
3	Correct	12 ms	1152 KB	Output is correct
4	Correct	15 ms	1280 KB	Output is correct
5	Correct	25 ms	1152 KB	Output is correct
6	Correct	41 ms	1188 KB	Output is correct
7	Correct	60 ms	1280 KB	Output is correct
8	Correct	381 ms	1784 KB	Output is correct
9	Correct	855 ms	2424 KB	Output is correct
10	Correct	2071 ms	3936 KB	Output is correct
11	Correct	2347 ms	3576 KB	Output is correct
12	Execution timed out	5031 ms	6280 KB	Time limit exceeded
13	Correct	4650 ms	6628 KB	Output is correct