Submission #160370

#	Time	Username	Problem	Language	Result	Execution time	Memory
160370		GioChkhaidze	Meteors (POI11_met)	C++14	100 / 100	4005 ms	40088 KiB

met

#include <bits/stdc++.h>

#define Tree int h,int l,int r
#define Left 2*h,l,(l+r)/2
#define Right 2*h+1,(l+r)/2,r
#define F first
#define S second

using namespace std;

const int N=300005;

long long n,m,q;
long long b[N],x[N];

int ANS[N];
int L[N],R[N],M[N];
int l[N],r[N],a[N];

vector < int > V[N];
vector < pair < int , int > > H;

long long G[N];

void Upd(int idx,long long delta)
{
    while (idx<=N+1) { G[idx]+=delta; idx+=(idx & -idx); }
}

long long Get(int idx)
{
    long long res=0;

    while (idx>0) { res+=G[idx]; idx-=(idx & -idx); }

    return res;
}

main ()
{
	ios::sync_with_stdio(false);
	
	cin>>n>>m;
	
    for (int i=1; i<=m; i++)
    {
        cin>>a[i];
        V[a[i]].push_back(i);
    }

    for (int i=1; i<=n; i++)
        cin>>b[i];

    cin>>q;

    for (int i=1; i<=q; i++)
        cin>>l[i]>>r[i]>>x[i];

    for (int i=1; i<=n; i++)
        L[i]=1,R[i]=q;

    for (int i=1; i<=30; i++)
    {
        H.clear();

        for (int j=1; j<=n; j++)
        {
            M[j]=(L[j]+R[j])/2;
            H.push_back({M[j],j});
        }

        sort(H.begin(),H.end());

        int Q=0;

        for (int j=0; j<=N-3; j++)
            G[j]=0;

        for (int j=0; j<H.size(); j++)
        {
        	if (R[H[j].S]<L[H[j].S]) continue;
        	
            while (Q+1<=H[j].F)
            {
                Q++;

                if (l[Q]>r[Q])
                {
                    Upd(1,x[Q]); Upd(r[Q]+1,-x[Q]);
                    Upd(l[Q],x[Q]); Upd(m+1,-x[Q]);
                }
                    else
                {
                    Upd(l[Q],x[Q]); 
					Upd(r[Q]+1,-x[Q]);
                }
            }

            long long int res=0;

            for (int k=0; k<V[H[j].S].size(); k++)
        	{
                res+=Get(V[H[j].S][k]);
         		if (res>1e9) res=1e10;
		 	}
             
            if (res>=b[H[j].S]) R[H[j].S]=M[H[j].S]-1,ANS[H[j].S]=H[j].F;
                           else L[H[j].S]=M[H[j].S]+1;
		}
    }

    for (int i=1; i<=n; i++)
        if (!ANS[i]) cout<<"NIE"<<endl;
                else cout<<ANS[i]<<endl;
}

Compilation message (stderr)

met.cpp:39:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main ()
       ^
met.cpp: In function 'int main()':
met.cpp:79:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j=0; j<H.size(); j++)
                       ~^~~~~~~~~
met.cpp:101:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int k=0; k<V[H[j].S].size(); k++)
                           ~^~~~~~~~~~~~~~~~~

• 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