Submission #870030

#	Time	Username	Problem	Language	Result	Execution time	Memory
870030		thienhx	Meteors (POI11_met)	C++17	74 / 100	647 ms	31324 KiB

met

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

using ll = long long;   
using str = string;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
//--------------------
#define          mp   make_pair
#define          F   first
#define          S   second
#define          pb   push_back
#define          eb   emplace_back
#define      all(x)   (x).begin(), (x).end()
#define       sz(x)   (int)((x).size())
#define    mem(f,x)   memset(f , x , sizeof(f))
#define     MASK(x)   (1ll << (x))
#define   cntbit(x)   __builtin_popcountll(x)
#define __lcm(a, b)   (1ll * ((a) / __gcd((a), (b))) * (b))
//--------------------
template<class T>inline bool maximize(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool minimize(T&a,const T&b){return a>b?a=b,1:0;}
#define PROBLEM "test"

const int MOD = 1e9 + 7; // 998244353;
const ll INF = 1e18;
const ld PI = acos(-1.0);
const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1}; // U R D L
 
//-----------------[PROBLEM SOLUTION]-----------------//

const int maxn = 3e5 + 15;
ll lim[maxn], amt[maxn], res[maxn], ind = 0;
pll range[maxn];
vector<ll> pos[maxn];

struct BIT1D {
    ll n;
    vector<ll> bit;

    BIT1D(ll _n) : n(_n) {
        bit.assign(n + 1, 0);
    }

    void reset() {
        for (int i = 0; i <= n; i++)
            bit[i] = 0;
    }

    ll Query(ll p) {
        ll res = 0;

        for (; p > 0; p -= (p & (-p)))
            res += bit[p];

        return res;
    }

    void Update(ll p, ll x) {
        for (; p <= n; p += (p & (-p)))
            bit[p] += x;
    }

    void Update2(ll l, ll r, ll x) {
        Update(l, x);
        Update(r + 1, -x);
    }
};

struct State {
    ll L, R;
    vector<ll> st;

    State() { }
};

void solve() {
    ll n, m, k;
    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        ll x;
        cin >> x;

        pos[x].pb(i);
    }
    for (int i = 1; i <= n; i++)
        cin >> lim[i];

    cin >> k;
    for (int i = 1; i <= k; i++)
        cin >> range[i].F >> range[i].S >> amt[i];

    State tmp;
    tmp.L = 1, tmp.R = k + 1;
    for (int i = 1; i <= n; i++) tmp.st.pb(i);

    BIT1D bit(m);
    queue<State> q;
    q.push(tmp);
    while(q.size()) {
        State cur = q.front(); q.pop();

        if(cur.L < cur.R) {
            ll mid = (cur.L + cur.R) / 2;

            if(ind > mid) ind = 0, bit.reset();
            while(ind < mid) {
                ind++;
                if(range[ind].F <= range[ind].S) bit.Update2(range[ind].F, range[ind].S, amt[ind]);
                else bit.Update2(range[ind].F, m, amt[ind]), bit.Update2(1, range[ind].S, amt[ind]);
            }

            State stL, stR;
            stL.L = cur.L, stL.R = mid;
            stR.L = mid + 1, stR.R = cur.R;
            for (int v : cur.st) {
                ll sum = 0;
                for (int p : pos[v])
                    sum += bit.Query(p);

                if(sum >= lim[v]) stL.st.pb(v);
                else stR.st.pb(v);
            }

            if(stL.st.size()) q.push(stL);
            if(stR.st.size()) q.push(stR);
        }
        else 
            for (int v : cur.st) res[v] = cur.R;
    }

    for (int i = 1; i <= n; i++) {
        if (res[i] <= k) cout << res[i] << '\n';
        else cout << "NIE" << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    if (fopen(PROBLEM".inp", "r")){
        freopen(PROBLEM".inp", "r", stdin);
        freopen(PROBLEM".out", "w", stdout);
    }

    constexpr bool MULTI_TEST = 0;
    int t = 1;
    if(MULTI_TEST) cin >> t;
    while(t--)
        solve();
}

Compilation message (stderr)

met.cpp: In function 'int main()':
met.cpp:145:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |         freopen(PROBLEM".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
met.cpp:146:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |         freopen(PROBLEM".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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