oj.uz

Submission #1015657

# Submission time Handle Problem Language Result Execution time Memory
1015657 2024-07-06T16:09:55 Z vjudge1 Meteors (POI11_met) C++17
62 / 100
 457 ms 65536 KB 
    //
    //  main1.cpp
    //  problem1
    //
    //  Created by Essa Almousa on 2030 / 01/ 01 AD.
    //

    #include <bits/stdc++.h>

    using namespace std;
    #define endl '\n'
    using ll = unsigned long long;
    using ll1 = long long;
    #define pb push_back
    #define pF first
    #define pS second
    #define SP <<" "<<
    const ll N = 3e5+10;

    struct segment {
        vector<ll> tree;
        ll offset = 1;
        void it(ll n) {
            while (offset < n) offset *= 2;
            tree.resize(offset*2, 0);
        }
        void upd(ll v, ll l, ll r, ll ql, ll qr, ll x) {
            if (l >= qr || r <= ql) return;
            if (l >= ql && r <= qr) {tree[v] += x; return;}
            ll mi = (l+r)/2;
            upd(v*2, l, mi, ql, qr, x);
            upd(v*2+1, mi, r, ql, qr, x);
        }
        ll query(ll i) {
            i--;
            i += offset;
            ll ans = 0;
            while (i >= 1) {
                ans += tree[i];
                i /= 2;
            }
            return ans;
        }
        void upd(ll l, ll r, ll val) {return upd(1, 0, offset, l-1, r, val);}
    };

    struct query_ {
        ll l, r, x;
    };
    ll a[N], b[N];
    ll1 sol[N];
    vector<ll> frq[N];
    query_ q[N];

    int main() {
        //ios::sync_with_stdio(0); cout.tie(0); cin.tie(0);
        ll n, m;
        cin>>n>>m;
        for (ll i=1; i<=m; i++) {
            cin>>a[i];
            frq[a[i]].pb(i);
        }
        
        for (ll i=1; i<=n; i++) cin>>b[i];
        
        ll q1;
        cin>>q1;
        
        struct binnode { ll i, m, l, r; };
        
        vector<binnode> bin[N];
        for (ll i=1; i<=n; i++) {
            ll mi = q1+1/2;
            bin[mi].pb({i, mi, 1, q1});
        }

        for (ll i=1; i<=q1; i++) {
            ll l, r, x;
            cin>>l>>r>>x;
            q[i] = {l, r, x};
            sol[i] = -1;
        }
        ll1 cnt = n;
        while (cnt > 0) {
            segment tree;
            tree.it(m);
            for (ll i=1; i<=q1; i++) {
                if (q[i].l > q[i].r) {
                    tree.upd(q[i].l, m, q[i].x);
                    tree.upd(1, q[i].r, q[i].x);
                }
                else tree.upd(q[i].l, q[i].r, q[i].x);
                
                for (ll1 j = bin[i].size()-1; j >= 0; j = bin[i].size()-1) {
                    binnode& x = bin[i][j];
                    ll ans = 0; // the num
                    for (ll k=0; k < frq[x.i].size(); k++) ans += tree.query(frq[x.i][k]);
                    if (ans >= b[x.i]) x.r = x.m;
                    else {
                        if (x.l >= q1) {cnt--;bin[i].pop_back(); continue;};
                        x.l = x.m+1;
                    }
                    ll mid = (x.l+x.r)/2;
                    if (x.l != x.r) {bin[mid].pb({x.i, mid, x.l, x.r}); cnt++;}
                    else sol[x.i] = x.l;
                    bin[i].pop_back();
                    cnt--;
                    j = bin[i].size() - 1;
                }
            }
        }
        for (ll i=1; i<=n; i++) {
            if (sol[i] == -1) cout << "NIE" << endl;
            else cout << sol[i] << endl;
        }
    }

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15708 KB Output is correct
2 Correct 7 ms 15708 KB Output is correct
3 Correct 7 ms 17888 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15704 KB Output is correct
2 Correct 7 ms 15896 KB Output is correct
3 Correct 7 ms 15964 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 19152 KB Output is correct
2 Correct 218 ms 20168 KB Output is correct
3 Correct 209 ms 27444 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 25196 KB Output is correct
2 Correct 213 ms 26760 KB Output is correct
3 Correct 257 ms 31836 KB Output is correct
4 Incorrect 37 ms 22224 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 21664 KB Output is correct
2 Correct 115 ms 27300 KB Output is correct
3 Correct 100 ms 17232 KB Output is correct
4 Correct 204 ms 29120 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 18872 KB Output is correct
2 Correct 195 ms 24936 KB Output is correct
3 Correct 176 ms 19908 KB Output is correct
4 Correct 249 ms 33340 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 445 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 457 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -