제출 #1195205

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1195205		hafo	Meteors (POI11_met)	C++20	87 / 100	6094 ms	64552 KiB

met

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 3e5 + 7;
const ll oo = (ll) 1e9 + 69;

int n, m, p[maxn], q, l[maxn], r[maxn];
vector<int> own[maxn];
vector<int> ev[maxn];
bool okAns[maxn];

int mul(const int &a, const int &b) {
    if(a > oo / b) return oo;
    return a * b;
}

int add(const int &a, const int &b) {
    if(a + b > oo) return oo;
    return a + b;
}

struct query {
    int l, r, val;
} que[maxn];

struct ST {
    int st[4 * maxn];
    int lz[4 * maxn];

    void init(int n) {
        for(int i = 1; i <= 4 * n; i++) {
            st[i] = lz[i] = 0;
        }
    }

    void fix(int id, int l, int r) {
        if(!lz[id]) return;
        st[id] = add(st[id], mul(lz[id], r - l + 1));
        if(l != r) {
            lz[id << 1] = add(lz[id << 1], lz[id]);
            lz[id << 1 | 1] = add(lz[id << 1 | 1], lz[id]);
        }
        lz[id] = 0;
    }

    void update(int id, int l, int r, int u, int v, int val) {
        fix(id, l, r);
        if(r < u || l > v) return;
        if(u <= l && r <= v) {
            lz[id] = add(lz[id], val);
            fix(id, l, r);
            return;
        }
        int mid = l + r >> 1;
        update(id << 1, l, mid, u, v, val);
        update(id << 1 | 1, mid + 1, r, u, v, val);
        st[id] = add(st[id << 1], st[id << 1 | 1]);
    }

    int get(int id, int l, int r, int u, int v) {
        fix(id, l, r);
        if(r < u || l > v) return 0;
        if(u <= l && r <= v) return st[id];
        int mid = l + r >> 1;
        return add(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
    }

} st;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    cin>>n>>m;
    for(int i = 1; i <= m; i++) {
        int x;
        cin>>x;
        own[x].pb(i);
    }
    for(int i = 1; i <= n; i++) {
        cin>>p[i];
    }
    cin>>q;
    for(int i = 1; i <= q; i++) {
        cin>>que[i].l>>que[i].r>>que[i].val;
    }
    for(int i = 1; i <= n; i++) {
        l[i] = 1;
        r[i] = q + 1;
    }

    while(1) {
        bool ok = 0;
        for(int i = 1; i <= n; i++) {
            if(l[i] < r[i]) ok = 1;
            ev[(l[i] + r[i]) >> 1].pb(i);
        }

        if(!ok) break;

        st.init(m);

        for(int i = 1; i <= q; i++) {
            if(que[i].l <= que[i].r) {
                st.update(1, 1, m, que[i].l, que[i].r, que[i].val);
            } else {
                st.update(1, 1, m, que[i].l, m, que[i].val);
                st.update(1, 1, m, 1, que[i].r, que[i].val);
            }

            while(!ev[i].empty()) {
                int j = ev[i].back();
                ev[i].pop_back();
                ll s = 0;
                for(auto x:own[j]) {
                    s += st.get(1, 1, m, x, x);
                    if(s >= p[j]) break;
                }
                if(s >= p[j]) {
                    r[j] = i;
                    okAns[j] = 1;
                }
                else l[j] = i + 1;
            }
        }
    }

    for(int i = 1; i <= n; i++) {
        if(!okAns[i]) cout<<"NIE\n";
        else cout<<l[i]<<"\n";
    }
    return 0;
}

• 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: 13 / 13