Submission #418840

#	Time	Username	Problem	Language	Result	Execution time	Memory
418840		lyc	Meteors (POI11_met)	C++14	100 / 100	1566 ms	38080 KiB

met

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

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)

const int mxN = 3e5+5;
const int mxM = 3e5+5;
const int mxK = 3e5+5;

int N, M, P[mxN], K;
vector<int> O[mxN];
struct Shower { int l, r, a; } showers[mxK];

struct Fenwick {
    long long ft[mxM];

    Fenwick() {
        memset(ft,0,sizeof ft);
    }

    void update(int a, int b) {
        for (; a <= M; a += a&-a) ft[a] += b;
    }

    inline void update(int a, int b, int c) {
        update(a,c);
        update(b+1,-c);
    }

    long long query(int a) {
        long long r = 0;
        for (; a; a -= a&-a) r += ft[a];
        return r;
    }
} ft;

int w[mxN];

void toggle(int l, int r, bool f) {
    FOR(i,l,r){
        auto& s = showers[i];
        int x = f ? s.a : -s.a;
        if (s.l <= s.r) {
            ft.update(s.l, s.r, x);
        } else {
            ft.update(s.l, M, x);
            ft.update(1, s.r, x);
        }
    }
}

void dnc(int l, int r, vector<int> nations) {
    if (l == r) {
        toggle(l,r,1);
        for (int& a : nations) {
            long long cur = 0;
            for (int& i : O[a]) {
                cur += ft.query(i);
                if (cur >= P[a]) break;
            }
            if (cur >= P[a]) w[a] = l;
            else w[a] = -1;
        }
        //cout << l << ": "; FOR(i,1,M){ cout << ft.query(i) << ' '; } cout << endl;
        toggle(l,r,0);
        return;
    }

    int m = (l+r)/2;
    //cout << l _ r << ": "; FOR(i,1,M){ cout << ft.query(i) << ' '; } cout << endl;
    toggle(l,m,1);

    //cout << l _ r << ": " << endl;
    vector<int> ls, rs;
    for (int& a : nations) {
        long long cur = 0;
        for (int& i : O[a]) {
            //TRACE(i _ ft.query(i));
            cur += ft.query(i);
            if (cur >= P[a]) break;
        }
        //cout << "\t" << a << " cur " << cur << " tgt " << P[a] << endl;
        if (cur >= P[a]) ls.push_back(a);
        else rs.push_back(a);
    }

    dnc(m+1,r,rs);
    toggle(l,m,0);
    //cout << l _ r << ": "; FOR(i,1,M){ cout << ft.query(i) << ' '; } cout << endl;
    dnc(l,m,ls);
}

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

    cin >> N >> M;
    FOR(i,1,M){
        int x; cin >> x;
        O[x].push_back(i);
    }
    FOR(i,1,N){
        cin >> P[i];
    }

    cin >> K;
    FOR(i,1,K){
        int L, R, A; cin >> L >> R >> A;
        showers[i] = {L,R,A};
    }

    vector<int> v(N);
    iota(ALL(v),1);

    dnc(1,K,v);

    FOR(i,1,N){
        if (w[i] == -1) cout << "NIE" << '\n';
        else cout << w[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: 13 / 13
• Subtask 8: 13 / 13