Submission #1046451

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1046451	2024-08-06T14:59:22 Z	qrno	Meteors (POI11_met)	C++14	100 / 100	1311 ms	65536 KB

#include <bits/stdc++.h>
using namespace std;

#define int long long

//{{{ FenwickTree
struct FenwickTree {
  int N;
  vector<int> data;

  FenwickTree(int N) : N(N), data(N) {}

  void add(int idx, int delta) {
    for (; idx < N; idx |= idx+1)
      data[idx] += delta;
  }

  int sum(int r) {
    int ret = 0;
    for (; r >= 0; r &= r+1, r--)
      ret += data[r];
    return ret;
  }

  int sum(int l, int r) {
    return sum(r) - sum(l-1);
  }
};
//}}}

// Range Fenwick {{{
struct RangeFenwick {
  FenwickTree FT;
  RangeFenwick(int N) : FT(N+1) {}

  void update(int l, int r, int x) {
    FT.add(l, x);
    FT.add(r+1, -x);
  }

  int query(int idx) {
    return FT.sum(idx);
  }
};
//}}}

const int LOG = 20;

// Debug {{{
#define var(x) "[", #x, " ", x, "] "
template<typename ...A> void db(A const&... a) { ((cout << (a)), ...); cout << endl; }
//}}}

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  int N, M;
  cin >> N >> M;

  vector<int32_t> O(M), P(N);
  for (auto &x : O) cin >> x, x--;
  for (auto &x : P) cin >> x;

  vector<vector<int32_t>> S(N);
  for (int i = 0; i < M; i++)
    S[O[i]].push_back(i);

  int K;
  cin >> K;

  vector<array<int32_t, 3>> Q(K);
  for (auto &[l, r, a] : Q) {
    cin >> l >> r >> a;
    l--, r--;
  }

  vector<vector<int32_t>> who(K+1);
  vector<int32_t> L(N, 0), R(N, K-1);
  vector<int32_t> ans(N, -1);

  for (int step = 0; step < LOG; step++) {
    for (int i = 0; i < N; i++) {
      if (L[i] > R[i]) continue;
      int mid = (L[i]+R[i])/2;
      who[mid].push_back(i);
    }

    RangeFenwick FT(M);
    for (int mid = 0; mid < K; mid++) {
      auto [l, r, x] = Q[mid];
      if (l <= r) {
        FT.update(l, r, x);
      } else {
        FT.update(l, M-1, x);
        FT.update(0, r, x);
      }

      for (auto v : who[mid]) {
        int sum = 0;
        for (auto s : S[v]) {
          sum += FT.query(s);
          if (sum >= P[v]) break;
        }
        if (sum >= P[v]) {
          ans[v] = mid;
          R[v] = mid-1;
        } else {
          L[v] = mid+1;
        }
      }
      who[mid].clear();
    }
  }

  for (auto x : ans) {
    if (x == -1) cout << "NIE" << endl;
    else cout << x+1 << endl;
  }
}

Compilation message

met.cpp: In function 'void db(const A& ...)':
met.cpp:51:66: warning: fold-expressions only available with '-std=c++17' or '-std=gnu++17'
   51 | template<typename ...A> void db(A const&... a) { ((cout << (a)), ...); cout << endl; }
      |                                                                  ^~~
met.cpp: In function 'int main()':
met.cpp:72:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |   for (auto &[l, r, a] : Q) {
      |              ^
met.cpp:90:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   90 |       auto [l, r, x] = Q[mid];
      |            ^

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	528 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	604 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	50 ms	3768 KB	Output is correct
2	Correct	111 ms	6604 KB	Output is correct
3	Correct	76 ms	5428 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	79 ms	4812 KB	Output is correct
2	Correct	81 ms	4964 KB	Output is correct
3	Correct	112 ms	6536 KB	Output is correct
4	Correct	27 ms	3528 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	51 ms	4040 KB	Output is correct
2	Correct	74 ms	6856 KB	Output is correct
3	Correct	28 ms	2136 KB	Output is correct
4	Correct	91 ms	6088 KB	Output is correct

Subtask #6
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	78 ms	3024 KB	Output is correct
2	Correct	84 ms	4816 KB	Output is correct
3	Correct	53 ms	3280 KB	Output is correct
4	Correct	114 ms	7736 KB	Output is correct

Subtask #7
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	902 ms	32112 KB	Output is correct
2	Correct	543 ms	15676 KB	Output is correct
3	Correct	133 ms	9304 KB	Output is correct
4	Correct	1213 ms	61392 KB	Output is correct

Subtask #8
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	875 ms	30776 KB	Output is correct
2	Correct	502 ms	15688 KB	Output is correct
3	Correct	121 ms	7452 KB	Output is correct
4	Correct	1311 ms	65536 KB	Output is correct