oj.uz

Submission #1008345

# Submission time Handle Problem Language Result Execution time Memory
1008345 2024-06-26T09:39:22 Z DucNguyen2007 Meteors (POI11_met) C++14
100 / 100
 1206 ms 38548 KB 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
using ll = unsigned long long;
using ld = long double;

const int N = 3e5 + 5;

int n, m, q;
int own[N];
int l[N], r[N];
int low[N], hig[N];
ll a[N], amount[N];
vector<int> adj[N];

struct BIT
{
    ll a[N];
    BIT()
    {
        memset(a, 0, sizeof a);
    }
    void clear()
    {
        memset(a, 0, sizeof a);
    }
    void Update(int p, ll v)
    {
        for(; p <= m; p += p & -p)
            a[p] += v;
    }
    ll Get(int p)
    {
        ll ans = 0;
        for(; p > 0; p -= p & -p)
            ans += a[p];
        return ans;
    }
} s;

void Read()
{
    cin >> n >> m;
    for(int i = 1; i <= m; ++i)
        cin >> own[i],
            adj[own[i]].push_back(i);
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    cin >> q;
    for(int i = 1; i <= q; ++i)
        cin >> l[i] >> r[i] >> amount[i];
}

void Update(int i)
{
    s.Update(l[i], amount[i]);
    s.Update(r[i] + 1, -amount[i]);
    if(l[i] > r[i])
        s.Update(1, amount[i]);
}

ll Get_Sum(int i)
{
    ll ans = 0;
    for(auto j : adj[i])
        ans += s.Get(j);
    return ans;
}

void Solve()
{
    vector<int> id[2];
    for(int i = 1; i <= n; ++i)
        id[0].push_back(i),
        low[i] = 1,
                 hig[i] = q;
    while(id[0].size())
    {
        sort(id[0].begin(), id[0].end(), [&](const int &x, const int &y)
        {
            return (low[x] + hig[x]) / 2 < (low[y] + hig[y]) / 2;
        });
        int piv = 1;
        for(auto j : id[0])
        {
            int mid = (low[j] + hig[j]) / 2;
            while(piv <= mid)
                Update(piv),
                ++piv;
            ll v = Get_Sum(j);
            if(v < a[j])
                low[j] = mid + 1;
            else
                hig[j] = mid - 1;
            if(low[j] <= hig[j])
                id[1].push_back(j);
        }
        swap(id[0], id[1]);
        id[1].clear();
        s.clear();
    }
    for(int i = 1; i <= n; ++i)
        if(low[i] > q)
            cout << "NIE\n";
        else
            cout << low[i] << "\n";
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    Read();
    Solve();
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 15028 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 3 ms 15048 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 15768 KB Output is correct
2 Correct 82 ms 18268 KB Output is correct
3 Correct 59 ms 16208 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 16004 KB Output is correct
2 Correct 67 ms 17872 KB Output is correct
3 Correct 97 ms 16724 KB Output is correct
4 Correct 20 ms 16088 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 15864 KB Output is correct
2 Correct 63 ms 18456 KB Output is correct
3 Correct 15 ms 15192 KB Output is correct
4 Correct 62 ms 16368 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 15448 KB Output is correct
2 Correct 78 ms 16008 KB Output is correct
3 Correct 47 ms 17564 KB Output is correct
4 Correct 75 ms 16704 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 881 ms 24192 KB Output is correct
2 Correct 132 ms 17760 KB Output is correct
3 Correct 100 ms 17524 KB Output is correct
4 Correct 1107 ms 36876 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 881 ms 23628 KB Output is correct
2 Correct 441 ms 17636 KB Output is correct
3 Correct 37 ms 18460 KB Output is correct
4 Correct 1206 ms 38548 KB Output is correct