답안 #870030

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
870030	2023-11-06T16:47:52 Z	thienhx	Meteors (POI11_met)	C++17	74 / 100	647 ms	31324 KB

#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

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.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	12888 KB	Output is correct
2	Correct	3 ms	12892 KB	Output is correct
3	Correct	4 ms	12976 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	12888 KB	Output is correct
2	Correct	3 ms	12892 KB	Output is correct
3	Correct	3 ms	12948 KB	Output is correct

Subtask #3
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	42 ms	14144 KB	Output is correct
2	Correct	75 ms	18408 KB	Output is correct
3	Correct	66 ms	16104 KB	Output is correct

Subtask #4
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	65 ms	14592 KB	Output is correct
2	Correct	67 ms	15876 KB	Output is correct
3	Correct	74 ms	18588 KB	Output is correct
4	Correct	22 ms	15212 KB	Output is correct

Subtask #5
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	55 ms	14416 KB	Output is correct
2	Correct	64 ms	18820 KB	Output is correct
3	Correct	18 ms	13400 KB	Output is correct
4	Correct	67 ms	16516 KB	Output is correct

Subtask #6
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	33 ms	13784 KB	Output is correct
2	Correct	71 ms	15940 KB	Output is correct
3	Correct	48 ms	15192 KB	Output is correct
4	Correct	80 ms	19256 KB	Output is correct

Subtask #7
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	547 ms	31324 KB	Output is correct
2	Incorrect	600 ms	29256 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #8
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	644 ms	30092 KB	Output is correct
2	Incorrect	647 ms	27600 KB	Output isn't correct
3	Halted	0 ms	0 KB	-