제출 #1292630

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1292630		aliete	새로운 문제 (POI11_met)	C++20	24 / 100	6094 ms	27388 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];
vector<int> ch[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=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]);
            }
            
            for(int st : ok)
            {
                if(ans[st] == 0)
                {
                    int be = cnt2[st];
                    vector<int> tmp(m+2);
                    
                    for(int j=ii-cn+1 ; j<=ii ; j++)
                    {
                        int lq = qu[j-1].S.F;
                        int rq = qu[j-1].S.S;
                        int vq = qu[j-1].F;
                        
                        if(lq <= rq)
                        {
                            tmp[lq] += vq;
                            tmp[rq+1] -= vq;
                        }
                        else
                        {
                            tmp[lq] += vq;
                            tmp[m+1] -= vq;
                            tmp[1]  += vq;
                            tmp[rq+1]-= vq;
                        }
                        
                        vector<int> pre(m+2);
                        for(int x=1 ; x<=m ; x++)
                            pre[x] = pre[x-1] + tmp[x];
                        
                        int cur = be;
                        for(int pos : ch[st])
                            cur += pre[pos];
                        
                        if(cur >= a[st])
                        {
                            ans[st] = j;
                            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";
    }
}

• Subtask 1: 12 / 12
• Subtask 2: 12 / 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