Submission #1169865

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169865		HoriaHaivas	Meteors (POI11_met)	C++20	100 / 100	899 ms	56932 KiB

met

#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
//#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r)
{
    return uniform_int_distribution<int>(l,r)(rng);
}

vector<int> poz[300005];
vector<int> queries[300005];
int req[300005];
int ans[300005];
int l[300005];
int r[300005];
int a[300005];
int m;

class AIB
{
public:
    unsigned long long aib[300005];
    void clr()
    {
        int i;
        for (i = 1; i <= m; i++)
        {
            aib[i]=0;
        }
    }
    void update(int idx, int delta)
    {
        while (idx <= m)
        {
            aib[idx]+=delta;
            idx+=idx&(-idx);
        }
    }
    void update(int l, int r, int x)
    {
        if (l > r)
        {
            update(l,m,x);
            update(1,r,x);
        }
        else
        {
            update(l,x);
            update(r+1,-x);
        }
    }
    unsigned long long query(int idx)
    {
        unsigned long long ans;
        ans=0;
        while (idx > 0)
        {
            ans+=aib[idx];
            idx-=idx&(-idx);
        }
        return ans;
    }
} aib;

signed main()
{
    //ifstream fin("sirbun.in");
    //ofstream fout("sirbun.out");
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,k,i,j,cnt,pas;
    unsigned long long score;
    cin >> n >> m;
    for (i = 1; i <= m; i++)
    {
        cin >> j;
        poz[j].push_back(i);
    }
    for (i = 1; i <= n; i++)
    {
        cin >> req[i];
    }
    cin >> k;
    for (i = 1; i <= k; i++)
    {
        cin >> l[i] >> r[i] >> a[i];
    }
    for (pas = 20; pas >= 0; pas--)
    {
        aib.clr();
        for (i = 1; i <= n; i++)
        {
            if (ans[i] + (1<<pas) <= k)
                queries[ans[i] + (1<<pas)].push_back(i);
        }
        for (i = 1; i <= k; i++)
        {
            aib.update(l[i],r[i],a[i]);
            for (auto x : queries[i])
            {
                score=0;
                for (auto y : poz[x])
                    score+=aib.query(y);
                if (score < req[x])
                    ans[x]+=(1<<pas);
            }
            queries[i].clear();
        }
    }
    for (i = 1; i <= n; i++)
    {
        ans[i]++;
        if (ans[i] <= k)
            cout << ans[i] << "\n";
        else
            cout << "NIE\n";
    }
    return 0;
}

• 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