oj.uz

Submission #421467

# Submission time Handle Problem Language Result Execution time Memory
421467 2021-06-09T07:50:21 Z 장태환(#7576) Bubble Sort 2 (JOI18_bubblesort2) C++17
0 / 100
 46 ms 1416 KB 
#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>>x;
int stree[1<<20];
int lazy[1<<20];
int treeN;
void ul(int n)
{
    stree[n]+=lazy[n];
    if(n<treeN)
    {
        lazy[n*2]+=lazy[n];
        lazy[n*2+1]+=lazy[n];
    }
    lazy[n]=0;
}
void upd(int s,int e,int qs,int qe,int i,int v)
{
    ul(i);
    if(s>qe||qs>e)
    {
        return;
    }
    if(qs<=s&&e<=qe)
    {
        lazy[i]+=v;
        ul(i);
        return;
    }
    upd(s,(s+e)/2,qs,qe,i*2,v);
    upd((s+e)/2+1,e,qs,qe,i*2+1,v);
    stree[i]=max(stree[i*2],stree[i*2+1]);
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V)
{
    int N=A.size();
	int Q=X.size();
	std::vector<int> answer(Q);
	for (int j=0;j<N;j++)
	{
		x.push_back({A[j],j});
	}
	for (int j=0;j<Q;j++)
	{
		x.push_back({V[j],X[j]});
	}
	sort(x.begin(),x.end());
	x.erase(unique(x.begin(),x.end()),x.end());
	for(treeN=1;treeN<x.size();treeN*=2);
	for(int j=0;j<N;j++)
	{
        int po=lower_bound(x.begin(),x.end(),make_pair(A[j],j))-x.begin();
        upd(0,treeN-1,po,po,1,j);
        upd(0,treeN-1,po+1,x.size()-1,1,-1);
	}
	for(int j=0;j<Q;j++)
	{
        int po=lower_bound(x.begin(),x.end(),make_pair(A[X[j]],X[j]))-x.begin();
        upd(0,treeN-1,po,po,1,-X[j]);
        upd(0,treeN-1,po+1,x.size()-1,1,1);
        po=lower_bound(x.begin(),x.end(),make_pair(V[j],X[j]))-x.begin();
        upd(0,treeN-1,po,po,1,X[j]);
        upd(0,treeN-1,po+1,x.size()-1,1,-1);
        answer[j]=stree[1];
	}
	return answer;
}

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for(treeN=1;treeN<x.size();treeN*=2);
      |              ~~~~~^~~~~~~~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 1416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -