Submission #981592

#	Time	Username	Problem	Language	Result	Execution time	Memory
981592		Tsagana	Painting Walls (APIO20_paint)	C++14	100 / 100	1074 ms	24956 KiB

paint

#include "paint.h"

//<TEMP>
#include<bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define pq priority_queue
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define F first
#define S second

using namespace std;
//</TEMP>
//OP
struct commands {
  const int inf = 1e9;
  int n;
  int m;
  int k;
  int cur;
  vector<int> C;
  vector<int> A;
  vector<int> mn;
  vector<int> ans;
  vector<vector<int>> B;
  vector<pair<int, int>> v;
  vector<pair<int, int>> go[200005];

  void set(int _N, int _M, int _K, vector<int> _C, vector<int> _A, vector<vector<int>> _B) {
    n = _N; m = _M; k = _K; C = _C; A = _A; B = _B;
    mn.resize(200005); ans.resize(200005);
    for (int i = 0; i < m; i++) for (auto j: B[i]) go[j].pb({i, 0});
  }

  int get(int x) {
    while (v.size() >= 2 && v[v.size()-2].F >= x) v.pop_back();
    return (v.back().F >= x ? v.back().S : inf);
  }

  int answer() {
    cur = 0; v.pb({-1, 0}); ans[0] = -1;

    for (int i = 0; i < n; i++) {
      for (auto &j: go[C[i]]) {
        j.S = (mn[j.F] != inf ? mn[j.F] : i);
        if (i - j.S + 1 >= m) {
          int x = get(i - m); if (x == inf) continue;
          ans[x + 1] = i; v.pb({i, x + 1}); cur = x + 1;
        }
      }
      if (i) for (auto j: go[C[i-1]]) mn[(j.F + 1) % m] = inf;
      for (auto j: go[C[i]]) mn[(j.F + 1) % m] = min(mn[(j.F + 1) % m], j.S);
    }
    return (ans[cur] < n - 1 ? -1 : cur);
  }
} cmd;

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
  cmd.set(N, M, K, C, A, B);
  return cmd.answer();
}
//ED

• Subtask 1: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 13 / 13
• Subtask 4: 23 / 23
• Subtask 5: 37 / 37