Submission #418840

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

Submission #418840

Compilation message