#include <bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;
#define pb push_back
#define P pair
#define F first
#define S second
struct segtree{
private:
struct node{
vector<int>count;
};
static node make_neutral(){
vector<int>A;
A.assign(101,0);
return{A};
}
static node single(int v){
vector<int>A;
A.assign(101,0);
A[v]++;
return{A};
}
static node merge(node &a,node &b){
node c{};
c.count.assign(101,0);
for(int i=0;i<101;i++){
c.count[i]=a.count[i]+b.count[i];
}
return c;
}
public:
int size;
vector<node>query;
void init(int n){
size=1;
while(size<n)size*=2;
query.assign(2*size,make_neutral());
}
void set(int i,int v,int x,int lx,int rx){
if(rx-lx==1){
query[x]=single(v);
return;
}
int m=(lx+rx)/2;
if(i<m)
set(i,v,2*x+1,lx,m);
else
set(i,v,2*x+2,m,rx);
query[x]=merge(query[2*x+1],query[2*x+2]);
}
void set(int i,int v){
set(i,v,0,0,size);
}
node calc(int l,int r,int x,int lx,int rx){
if(lx>=r || rx<=l)
return make_neutral();
if(l<=lx && rx<=r)
return query[x];
int m=(lx+rx)/2;
node a=calc(l,r,2*x+1,lx,m);
node b=calc(l,r,2*x+2,m,rx);
return merge(a,b);
}
vector<int> calc(int l,int r){
return calc(l,r,0,0,size).count;
}
};
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
int Q=X.size();
std::vector<int> answer;
int n=A.size();
stack<P<int,int>> best[101];
segtree tree;
tree.init(n);
for(int i=0;i<n;i++)
tree.set(i,A[i]);
for(int i=0;i<n;i++){
vector<int>c=tree.calc(0,i+1);
int calc=0;
for(int j=A[i]+1;j<=100;j++){
calc+=c[j];
}
best[A[i]].push({i,calc});
}
for(int i=0;i<Q;i++){
int prev=A[X[i]];
int nex=V[i];
int ind=X[i];
tree.set(ind,nex);
A[ind]=nex;
if(ind==best[prev].top().F){
best[prev].pop();
if(!best[prev].empty()){
vector<int>c=tree.calc(0,best[prev].top().F+1);
int calc=0;
for(int j=prev+1;j<=100;j++){
calc+=c[j];
}
best[prev].top().S=calc;
}
}
if(best[nex].empty()){
vector<int>c=tree.calc(0,ind+1);
int calc=0;
for(int j=nex+1;j<=100;j++){
calc+=c[j];
}
best[nex].push({ind,calc});
}
else {
if (ind > best[nex].top().F) {
vector<int> c = tree.calc(0, ind+1);
int calc = 0;
for (int j = nex + 1; j <= 100; j++) {
calc += c[j];
}
best[nex].push({ind, calc});
}
}
for(int j=1;j<=100;j++){
if(!best[j].empty()) {
if (best[j].top().F > ind) {
if (nex > A[best[j].top().F] && A[best[j].top().F] >= prev) {
best[j].top().S++;
}
if (nex <= A[best[j].top().F] && A[best[j].top().F] < prev) {
best[j].top().S--;
}
}
}
}
int max_d=0;
for(int j=1;j<=100;j++){
if(!best[j].empty()) {
max_d = max(max_d, best[j].top().S);
}
}
answer.pb(max_d);
}
return answer;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
2392 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
2392 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
140 ms |
29264 KB |
Output is correct |
| 2 |
Correct |
334 ms |
58452 KB |
Output is correct |
| 3 |
Correct |
472 ms |
59348 KB |
Output is correct |
| 4 |
Correct |
491 ms |
59460 KB |
Output is correct |
| 5 |
Correct |
454 ms |
59364 KB |
Output is correct |
| 6 |
Correct |
450 ms |
59448 KB |
Output is correct |
| 7 |
Correct |
451 ms |
59444 KB |
Output is correct |
| 8 |
Incorrect |
465 ms |
59472 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
2392 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
