oj.uz

Submission #160370

# Submission time Handle Problem Language Result Execution time Memory
160370 2019-10-27T08:15:59 Z GioChkhaidze Meteors (POI11_met) C++14
100 / 100
 4005 ms 40088 KB 
#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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 9848 KB Output is correct
2 Correct 19 ms 9848 KB Output is correct
3 Correct 19 ms 9848 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 9848 KB Output is correct
2 Correct 19 ms 9848 KB Output is correct
3 Correct 23 ms 9852 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 12280 KB Output is correct
2 Correct 343 ms 13696 KB Output is correct
3 Correct 232 ms 13012 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 12796 KB Output is correct
2 Correct 234 ms 12796 KB Output is correct
3 Correct 391 ms 13688 KB Output is correct
4 Correct 123 ms 11768 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 12292 KB Output is correct
2 Correct 388 ms 13832 KB Output is correct
3 Correct 84 ms 11128 KB Output is correct
4 Correct 246 ms 13360 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 12152 KB Output is correct
2 Correct 269 ms 13184 KB Output is correct
3 Correct 221 ms 12304 KB Output is correct
4 Correct 346 ms 13816 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1934 ms 31532 KB Output is correct
2 Correct 259 ms 24948 KB Output is correct
3 Correct 547 ms 16120 KB Output is correct
4 Correct 3506 ms 37944 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1818 ms 30284 KB Output is correct
2 Correct 705 ms 23284 KB Output is correct
3 Correct 124 ms 16448 KB Output is correct
4 Correct 4005 ms 40088 KB Output is correct