Submission #1292646

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292646		aliete	Meteors (POI11_met)	C++20	0 / 100	1431 ms	131072 KiB

met

// In the name of Allah //
#include <bits/stdc++.h>
using namespace std;
#define int 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=3e5+5 , mod=1e9+7 , inf=1e18;

int n , m , sq , cnt2[N];
int g[N] , p[N] , a[N] , ans[N] , cnt[N] , cur[N];
vector<int> ch[N];
bool is[N] , vis[N];

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    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];
    
    int q , cn=0 , ii=0;
    cin >> q;
    
    sq = max(1ll , (long long)sqrt(q));
    vector<pip> qu;
    
    while(q--)
    {
        int l , r , v;
        cin >> l >> r >> v;
        ii++ , cn++;
        
        qu.pb({v , {l , r}});
    
        if(l <= r)
        {
            p[l] += v;
            p[r+1]-=v;
        }
        else
        {
            p[l] += v;
            p[m+1]-=v;
            p[1] += v;
            p[r+1]-=v;
        }
        
        if(cn==sq || q==0)
        {
            vector<int> ok;

            for(int i=0 ; i<=n ; i++) 
				is[i] = false;
            
            for(int i=1 ; i<=m+1 ; i++)
                p[i] += p[i-1];
            
            for(int i=1 ; i<=n ; i++)
                cnt2[i] = cnt[i];
            
            for(int i=1 ; i<=m ; i++)
            {
                cnt[g[i]] += p[i];
                if(cnt[g[i]] >= a[g[i]] && cnt2[g[i]] < a[g[i]])
                    ok.pb(g[i]) , is[g[i]]=true;
            }
            
			if(!ok.empty())
            {
				int bs = ii - cn + 1;
				int be = ii;
				
                vector<pii> pl;
                pl.reserve(1024);
                for(int st : ok)
                    for(int pos : ch[st])
                        pl.pb({pos, st});
                
                for(int st : ok)
				{
                    cur[st] = cnt2[st];
                    vis[st] = true;
                }
                
                bool is3 = false;
                for(int j = bs; j <= be; j++)
                {
                    int lq = qu[j-1].S.F;
                    int rq = qu[j-1].S.S;
                    int vq = qu[j-1].F;
                    
                    for(auto &pr : pl)
                    {
                        int pos = pr.F;
                        int st = pr.S;
                        if(!vis[st]) continue;
                        bool is2 = false;
                        if(lq <= rq)
                        {
                            if(pos >= lq && pos <= rq) is2 = true;
                        }
                        else
                        {
                            if(pos >= lq || pos <= rq) is2 = true;
                        }
                        if(is2)
                        {
                            cur[st] += vq;
                            if(cur[st] >= a[st])
                            {
                                if(ans[st] == 0) ans[st] = j;
                                vis[st] = false;
                                is3 = true;
                            }
                        }
                    }
                }
                if(is3)
                {
                	int w = 0;
                	for(auto &pr : pl)
                	{
                		int st = pr.S;
                		if(vis[st]) pl[w] = pr , w++;
					}
				}
                for(int st : ok) vis[st] = false;
            }
            
            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";
    }
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13