# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
421513 |
2021-06-09T08:35:34 Z |
장태환(#7576) |
Cats or Dogs (JOI18_catdog) |
C++17 |
|
0 ms |
0 KB |
#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>>x;
int stree[1<<21];
int lazy[1<<2];
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);
upd(0,treeN-1,0,treeN-1,1,-1000000);
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+1000000);
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]-1000000);
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]+1000000);
upd(0,treeN-1,po+1,x.size()-1,1,-1);
answer[j]=stree[1];
A[X[j]]=V[j];
}
return answer;
}
Compilation message
catdog.cpp:1:10: fatal error: bubblesort2.h: No such file or directory
1 | #include "bubblesort2.h"
| ^~~~~~~~~~~~~~~
compilation terminated.