Submission #1049669

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1049669	2024-08-09T03:46:04 Z	QuangBui	Meteors (POI11_met)	C++14	61 / 100	701 ms	34004 KB

// QuangBuiCP
// https://oj.uz/problem/view/POI11_met
#include "bits/stdc++.h"
using namespace std;

int main() {
#ifndef LOCAL
  cin.tie(nullptr)->sync_with_stdio(false);
#endif // LOCAL

  int n, m;
  cin >> n >> m;
  vector<vector<int>> properties(n);
  for (int i = 0; i < m; ++i) {
    int who;
    cin >> who;
    properties[--who].push_back(i);
  }
  vector<int> target(n);
  for (int& it : target) {
    cin >> it;
  }
  int events;
  cin >> events;
  vector<tuple<int, int, int>> event(events);
  for (auto& [l, r, collectable] : event) {
    cin >> l >> r >> collectable;
    l--, r--;
  }

  vector<vector<int>> candidates(events + 1);
  vector<int> L(n, 0), R(n, events - 1);
  vector<int> answer(n, -1);
  for (int step = 0; step < 20; ++step) {
    for (int i = 0; i < n; ++i) {
      if (L[i] > R[i]) {
        continue;
      }
      int mid = (L[i] + R[i]) / 2;
      candidates[mid].push_back(i);
    }
    vector<int> fenw(m + 1, 0);
    auto Update = [&fenw, &m](int x, int val) {
      while (x <= m) {
        fenw[x] += val;
        x |= x + 1;
      }
    };
    auto UpdateRange = [&fenw, &m, &Update](int l, int r, int val) {
      Update(l, val);
      Update(r + 1, -val);
    };
    auto Query = [&fenw](int x) {
      int res = 0;
      while (x >= 0) {
        res += fenw[x];
        x &= x + 1;
        x--;
      }
      return res;
    };
    for (int mid = 0; mid < events; ++mid) {
      auto [l, r, collectable] = event[mid];
      if (l <= r) {
        UpdateRange(l, r, collectable);
      } else {
        UpdateRange(l, m - 1, collectable);
        UpdateRange(0, r, collectable);
      }
      for (int who : candidates[mid]) {
        int sum = 0;
        for (int land : properties[who]) {
          sum += Query(land);
        }
        if (sum >= target[who]) {
          answer[who] = mid;
          R[who] = mid - 1;
        } else {
          L[who] = mid + 1;
        }
      }
      candidates[mid].clear();
    }
  }

  for (int x : answer) {
    if (x == -1) {
      cout << "NIE\n";
    } else {
      cout << x + 1 << '\n';
    }
  }

  return 0;
}

Compilation message

met.cpp: In function 'int main()':
met.cpp:26:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |   for (auto& [l, r, collectable] : event) {
      |              ^
met.cpp:63:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |       auto [l, r, collectable] = event[mid];
      |            ^

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	464 KB	Output is correct
3	Correct	2 ms	348 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	532 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	3992 KB	Output is correct
2	Correct	71 ms	7052 KB	Output is correct
3	Correct	56 ms	5776 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	58 ms	5260 KB	Output is correct
2	Correct	58 ms	5260 KB	Output is correct
3	Correct	76 ms	7052 KB	Output is correct
4	Correct	16 ms	3480 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	4492 KB	Output is correct
2	Correct	47 ms	7312 KB	Output is correct
3	Correct	27 ms	2648 KB	Output is correct
4	Correct	61 ms	6364 KB	Output is correct

Subtask #6
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	62 ms	3520 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	699 ms	34004 KB	Output is correct
2	Incorrect	503 ms	17588 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #8
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	701 ms	32396 KB	Output is correct
2	Incorrect	457 ms	16640 KB	Output isn't correct
3	Halted	0 ms	0 KB	-