제출 #1008345

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1008345		DucNguyen2007	Meteors (POI11_met)	C++14	100 / 100	1206 ms	38548 KiB

met

#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 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13