oj.uz

답안 #418840

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
418840 2021-06-06T04:10:29 Z lyc Meteors (POI11_met) C++14
100 / 100
 1566 ms 38080 KB 
#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.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 9676 KB Output is correct
2 Correct 8 ms 9740 KB Output is correct
3 Correct 8 ms 9776 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 9804 KB Output is correct
2 Correct 7 ms 9744 KB Output is correct
3 Correct 8 ms 9804 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 12100 KB Output is correct
2 Correct 129 ms 15556 KB Output is correct
3 Correct 105 ms 12360 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 12168 KB Output is correct
2 Correct 111 ms 12184 KB Output is correct
3 Correct 120 ms 14392 KB Output is correct
4 Correct 35 ms 11972 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 11808 KB Output is correct
2 Correct 101 ms 14624 KB Output is correct
3 Correct 56 ms 10884 KB Output is correct
4 Correct 106 ms 12764 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 11520 KB Output is correct
2 Correct 103 ms 12312 KB Output is correct
3 Correct 83 ms 11752 KB Output is correct
4 Correct 121 ms 13624 KB Output is correct

Subtask #7
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1095 ms 35628 KB Output is correct
2 Correct 750 ms 22368 KB Output is correct
3 Correct 261 ms 15148 KB Output is correct
4 Correct 1309 ms 33372 KB Output is correct

Subtask #8
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1155 ms 32264 KB Output is correct
2 Correct 710 ms 20940 KB Output is correct
3 Correct 223 ms 15556 KB Output is correct
4 Correct 1566 ms 38080 KB Output is correct