Submission #1292653

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292653		aliete	Meteors (POI11_met)	C++20	100 / 100	1579 ms	27072 KiB

met

// In the name of Allah //
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define S second
#define F first
typedef pair<int,int> pii;
typedef pair<int,pii> pip;
const int N=300000+5;
const int inf = 1e9;

int n , m , sq;
int g[N];
ll p[N];
int a[N];
int ans[N];
ll cnt[N];
ll cnt2[N];
vector<int> ch[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    cin >> n >> m;
    for(int i=1 ; i<=m ; i++)
	{
        cin >> g[i];
        ch[g[i]].pb(i);
    }
    for(int i=1 ; i<=n ; i++) 
		cin >> a[i];

    cin >> q;
    sq = max(1 , (int)sqrt(q));

    vector<pip> qu;
    qu.reserve(q+5);

    int ii = 0;
    int cn = 0;

    while(q--)
    {
        int l , r , v;
        cin >> l >> r >> v;
        ii++; cn++;

        qu.pb({v,{l,r}});

        if(l <= r)
        {
            p[l] += v;
            if(r+1 <= m) p[r+1] -= v;
        }
        else
        {
            p[l] += v;
            if(m+1 <= m+1) p[m+1] -= v;
            p[1] += v;
            if(r+1 <= m) p[r+1] -= v;
        }

        if(cn == sq || q == 0)
        {
            for(int i=1 ; i<=m ; i++) 
				p[i] += p[i-1];

            for(int i=1 ; i<=n ; i++) 
				cnt2[i] = cnt[i];

            for(int i=1 ; i<=m ; i++)
			{
                if(p[i] != 0) 
				{
                    cnt[g[i]] += p[i];
                }
            }

            vector<int> ok;
            ok.reserve(64);
            for(int i=1 ; i<=n ; i++)
			{
                if(cnt[i] >= a[i] && cnt2[i] < a[i]) ok.pb(i);
            }

            int si = ii - cn;
            int ei = ii - 1;

            for(int st : ok)
            {
                if(ans[st] != 0) continue;
                ll cur = cnt2[st];
                for(int j=si ; j<=ei ; j++)
                {
                    int lq = qu[j].S.F;
                    int rq = qu[j].S.S;
                    int vq = qu[j].F;

                    int add_cnt = 0;
                    if(!ch[st].empty())
					{
                        if(lq <= rq)
						{
                            auto lo = lower_bound(ch[st].begin(), ch[st].end(), lq);
                            auto hi = upper_bound(ch[st].begin(), ch[st].end(), rq);
                            add_cnt = int(hi - lo);
                        } 
						else 
						{
                            auto lo1 = lower_bound(ch[st].begin(), ch[st].end(), lq);
                            auto hi1 = upper_bound(ch[st].begin(), ch[st].end(), m);
                            auto lo2 = lower_bound(ch[st].begin(), ch[st].end(), 1);
                            auto hi2 = upper_bound(ch[st].begin(), ch[st].end(), rq);
                            add_cnt = int(hi1 - lo1) + int(hi2 - lo2);
                        }
                    }

                    if(add_cnt) cur += 1LL * add_cnt * vq;

                    if(cur >= a[st])
					{
                        ans[st] = j + 1;
                        break;
                    }
                }
            }

            for(int i=1 ; i<=m+1 ; i++) p[i] = 0;

            cn = 0;
        }
    }

    for(int i=1; i<=n; ++i){
        if(ans[i] != 0) 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