제출 #1169518

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1169518		HoriaHaivas	Meteors (POI11_met)	C++20	74 / 100	882 ms	90636 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);
}

struct info
{
    int l;
    int r;
};



vector<int> poz[300005];
vector<info> interval;
vector<int> queries[1200005];
vector<int> curr;
vector<int> nxt;
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,lson,rson,pas;
    unsigned long long score;
    cin >> n >> m;
    for (i=1; i<=m; i++)
    {
        cin >> j;
        poz[j].push_back(i);
    }
    cnt=1;

    for (i=1; i<=n; i++)
    {
        cin >> req[i];
        queries[cnt].push_back(i);
    }

    cin >> k;
    interval.push_back({0,0});
    interval.push_back({1,k});
    curr.push_back(cnt);
    for (i=1; i<=k; i++)
    {
        cin >> l[i] >> r[i] >> a[i];
    }

    for (pas=20; pas>=0; pas--)
    {
        aib.clr();
        for (auto x : curr)
        {
            if (interval[x].l!=interval[x].r)
            {
                int mid;
                mid=(interval[x].l+interval[x].r)/2;
                cnt++;
                lson=cnt;
                interval.push_back({0,0});
                interval[cnt].l=interval[x].l;
                interval[cnt].r=mid;
                nxt.push_back(cnt);
                cnt++;
                rson=cnt;
                interval.push_back({0,0});
                interval[cnt].l=mid+1;
                interval[cnt].r=interval[x].r;
                nxt.push_back(cnt);
                for (i=interval[x].l; i<=mid; i++)
                    aib.update(l[i],r[i],a[i]);
                for (auto y : queries[x])
                {
                    score=0;
                    for (auto z : poz[y])
                        score+=aib.query(z);
                    if (score>=req[y])
                        queries[lson].push_back(y);
                    else
                        queries[rson].push_back(y);
                }
                for (i=mid+1; i<=interval[x].r; i++)
                    aib.update(l[i],r[i],a[i]);
            }
            else
            {
                for (i=interval[x].l; i<=interval[x].l; i++)
                    aib.update(l[i],r[i],a[i]);
                for (auto y : queries[x])
                {
                    score=0;
                    for (auto z : poz[y])
                        score+=aib.query(z);
                    if (score>=req[y])
                        ans[y]=interval[x].l;
                    else
                        ans[y]=-1;
                }
                nxt.push_back(x);
                queries[x].clear();
            }
        }
        curr.clear();
        swap(nxt,curr);
    }
    for (i=1; i<=n; i++)
    {
        if (ans[i]!=-1)
            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: 0 / 13
• Subtask 8: 0 / 13