oj.uz

Submission #418640

# Submission time Handle Problem Language Result Execution time Memory
418640 2021-06-05T16:15:19 Z lyc Meteors (POI11_met) C++14
0 / 100
 1142 ms 35740 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[mxN];

    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]) w[a] = l;
        }
        toggle(l,r,0);
        return;
    }

    int m = (l+r)/2;
    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);
        }
        //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);
    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);

    FOR(i,1,N) w[i] = -1;
    dnc(1,K,v);

    FOR(i,1,N){
        if (w[i] == -1) cout << "NIE" << '\n';
        else cout << w[i] << '\n';
    }
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 9676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9804 KB Output is correct
2 Correct 7 ms 9804 KB Output is correct
3 Incorrect 7 ms 9776 KB Output isn't correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 12136 KB Output is correct
2 Correct 124 ms 15400 KB Output is correct
3 Incorrect 102 ms 12408 KB Output isn't correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 109 ms 12156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 93 ms 11784 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 11616 KB Output is correct
2 Correct 108 ms 12324 KB Output is correct
3 Incorrect 83 ms 11756 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1142 ms 35740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1114 ms 32164 KB Output isn't correct
2 Halted 0 ms 0 KB -