제출 #1049625

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1049625		Persia	Meteors (POI11_met)	C++14	0 / 100	35 ms	65536 KiB

met

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define bit(i, x) (x >> i & 1)
#define _unique(x) (x).resize(unique((x).begin(), (x).end()) - (x).begin());
#define all(x) (x).begin(), (x).end()
using namespace std;
using namespace __gnu_pbds;
template<class T> using ordered_set =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
const int N = 3e5 + 3;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r) {
    return l+rng()%(r-l+1);
}
template<typename T> void cmax(T &a, T b) {a = max(a, b);}


int n, m, k;
vector<int> a[N];
int b[N];
tuple<int, int, int> q[N];

long long bit[N];
int L[N], R[N], ans[N];
stack<int> qq[N];

void update(int x, int d) {
    for(int i = x; i <= m; i += (i & -i)) {
        bit[i] += d;
    }
}

long long get(int x) {
    long long sum = 0;
    for(int i = x; i; i -= (i & -i)) {
        sum += bit[i];
    }
    return sum;
}

void update(int l, int r, int w) {
    if (l <= r) {
        update(l, w);
        update(r + 1, -w);
    }
    else {
        update(l, w);
        update(1, w);
        update(r + 1, -w);
    }
}

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

//    freopen("testing.txt", "r", stdin);
//    freopen("outputing.txt", "w", stdout);

//    freopen("divisors.inp", "r", stdin);
//    freopen("divisors.out", "w", stdout);
//    #define Kawaii
    #ifdef Kawaii
        auto starttime = chrono::high_resolution_clock::now();
    #endif

    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int x; cin >> x;
        a[x].push_back(i);
    }
    for(int i = 1; i <= n; i++) cin >> b[i];
    cin >> k;
    for(int i = 1; i <= k; i++) {
        int l, r, w; cin >> l >> r >> w;
        q[i] = make_tuple(l, r, w);
    }

    for(int i = 1; i <= n; i++) {
        L[i] = 1, R[i] = k, ans[i] = -1;
    }

    bool flag = 1;
    while (flag) {
        flag = 0;
        for(int i = 1; i <= n; i++) {
            if (L[i] <= R[i]) {
                int mid = (L[i] + R[i]) >> 1;
                qq[mid].push(i);
//                if (i == 1) cout << mid << " ";
            }
        }
        for(int i = 1; i <= k; i++) {
            update(get<0>(q[i]), get<1>(q[i]), get<2>(q[i]));
            while (!qq[i].empty()) {
                flag = 1;
                int u = qq[i].top();
                qq[i].pop();

                long long sum = 0;
                for(auto x : a[u]) {
                    sum += get(x);
                    if (sum >= b[u]) break;
                }
                if (sum >= b[u]) ans[u] = i, R[u] = i - 1;
                else L[u] = i + 1;
            }
        }
        for(int i = 1; i <= m; i++) bit[i] = 0;
    }

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

//    update(4, 2, 4);
//    update(1, 3, 1);
//    for(int i = 1; i <= m; i++) cout << get(i) << " ";

    #ifdef Kawaii
        auto endtime = chrono::high_resolution_clock::now();
        auto duration = chrono::duration_cast<chrono::milliseconds>(endtime - starttime).count();
        cerr << "\n=====" << "\nUsed: " << duration << " ms\n";
    #endif
}
// Changing for a better ending -_-

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