Submission #1344167

#	Time	Username	Problem	Language	Result	Execution time	Memory
1344167		altern23	Meteors (POI11_met)	C++20	74 / 100	702 ms	51668 KiB

met

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

#define ll long long

struct BIT {
      ll N;
      vector <ll> bit;
      BIT (ll _n) {
            N = _n;
            bit.resize(N+5);
      }

      void update(ll idx, ll val) {
            for (; idx <= N; idx += idx & -idx) bit[idx] += val;
      }

      ll get(ll idx) {
            ll ans = 0;
            for (; idx >= 1; idx -= idx & -idx) ans += bit[idx];
            return ans;
      }
};

int main() {
      ios_base::sync_with_stdio(0); cin.tie(0);
      int tc = 1;
      // cin >> tc;
      while (tc--) {
            ll N, M; cin >> N >> M;
            vector <ll> pos[N+5];
            for (int i = 1; i <= M; i++) {
                  ll x; cin >> x;
                  pos[x].push_back(i);
            }
            vector <ll> P(N+5);
            for (int i = 1; i <= N; i++) {
                  cin >> P[i];
            }
            ll K; cin >> K;
            vector <ll> L(K+5), R(K+5), A(K+5);
            for (int i = 1; i <= K; i++) {
                  cin >> L[i] >> R[i] >> A[i];
            }

            vector <ll> lf(N+5), rg(N+5), mid(N+5), ans(N+5, -1);
            vector <ll> query[K+5], nQuery[K+5];

            for (int i = 1; i <= N; i++) {
                  lf[i] = 1, rg[i] = K, mid[i] = (lf[i]+rg[i])/2;
                  query[mid[i]].push_back(i);
            }

            for (int log = 0; log < 20; log++) {
                  BIT bit(M);
                  for (int i = 1; i <= K; i++) {
                        if (L[i] <= R[i]) {
                              bit.update(L[i], A[i]);
                              bit.update(R[i]+1, -A[i]);
                        }
                        else {
                              bit.update(L[i], A[i]);
                              bit.update(1, A[i]);
                              bit.update(R[i]+1, -A[i]);
                        }
                        while (!query[i].empty()) {
                              ll x = query[i].back(); query[i].pop_back();
                              ll tot = 0;
                              for (auto y : pos[x]) {
                                    tot += bit.get(y);
                              }
                              if (tot >= P[x]) {
                                    ans[x] = i;
                                    rg[x] = mid[x]-1;
                              }
                              else {
                                    lf[x] = mid[x]+1;
                              }
                              if (lf[x] <= rg[x]) {
                                    mid[x] = (lf[x]+rg[x])/2;
                                    nQuery[mid[x]].push_back(x);
                              }
                        }
                  }
                  for (int i = 1; i <= K; i++) {
                        query[i].swap(nQuery[i]);
                  }
            }

            for (int i = 1; i <= N; i++) {
                  if (ans[i] == -1) cout << "NIE\n";
                  else cout << ans[i] << "\n";
            }
      }
}

/*

*/

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13