#include <bits/stdc++.h>
#include "bubblesort2.h"
#define orta ((bas + son)/2)
#define sol (k+k)
#define sag (k+k+1)
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define N 1000005
using namespace std;
typedef vector < int > vi;
int n, m, q, yer[4*N], yerl[4*N], cvp[4*N], cvpl[4*N];
set < int > s[N];
void yerput(int k, int bas, int son, int l);
void yerpush(int k, int bas, int son);
void yerset(int k, int bas, int son, int x, int y);
void yerup(int k, int bas, int son, int x, int y, int z);
int yerqu(int k, int bas, int son, int x);
void cvpput(int k, int bas, int son, int l);
void cvppush(int k, int bas, int son);
void cvpset(int k, int bas, int son, int x, int y);
void cvpup(int k, int bas, int son, int x, int y, int z);
int cvpqu(int k, int bas, int son, int x);
vi countScans(vi a, vi b, vi c){
vi ans;
n = a.size();
m = 100;
q = b.size();
for(int i = 0; i < n; i++)
s[a[i]].insert(i);
vi d = a;
sort(d.begin(), d.end());
for(int i = 0; i < n; i++){
if(i + 1 != n and d[i + 1] == d[i])
continue;
yerset(1, 1, m, d[i], i);
}
for(int i = 0; i < n; i++){
int son = *s[a[i]].rbegin();
int yr = yerqu(1, 1, m, a[i]);
cvpset(1, 1, m, a[i], son - yr);
}
for(int i = 0; i < q; i++){
int yr = b[i];
int yeni = c[i];
int eski = a[b[i]];
s[eski].erase(yr);
s[yeni].insert(yr);
// cout << eski << " " << yeni << endl;
if(eski < yeni){
yerup(1, 1, m, eski, yeni - 1, -1);
cvpup(1, 1, m, eski + 1, yeni - 1, 1);
if(!s[eski].empty())
cvpset(1, 1, m, eski, *s[eski].rbegin() - yerqu(1, 1, m, eski) );
cvpset(1, 1, m, yeni, *s[yeni].rbegin() - yerqu(1, 1, m, yeni) );
}
if(eski > yeni){
yerup(1, 1, m, yeni, eski - 1, 1);
cvpup(1, 1, m, yeni + 1, eski - 1, -1);
if(!s[eski].empty())
cvpset(1, 1, m, eski, *s[eski].rbegin() - yerqu(1, 1, m, eski) );
cvpset(1, 1, m, yeni, *s[yeni].rbegin() - yerqu(1, 1, m, yeni) );
}
ans.pb(cvp[1]);
}
return ans;
}
// int main(){
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// int n,q;
// scanf("%d %d",&n ,&q);
// vi a(n);
// for(int i=0;i<n;i++)
// scanf("%d",&a[i]);
// vi b(q), c(q);
// for(int j=0;j<q;j++){
// scanf("%d %d",&b[j], &c[j]);
// }
// vi cvp = countScans(a, b, c);
// for(int j=0;j<int(cvp.size());j++)
// printf("%d\n",cvp[j]);
// }
void yerput(int k, int bas, int son, int l){
yer[k] += (son - bas + 1)*l;
yerl[k] += l;
}
void yerpush(int k, int bas, int son){
yerput(sol, bas, orta, yerl[k]);
yerput(sag, orta + 1, son, yerl[k]);
yerl[k] = 0;
}
void yerset(int k, int bas, int son, int x, int y){
if(bas == son){
yer[k] = y;
return;
}
yerpush(k, bas, son);
if(x <= orta)
yerset(sol, bas, orta, x, y);
else
yerset(sag, orta + 1, son, x, y);
yer[k] = yer[sol] + yer[sag];
}
void yerup(int k, int bas, int son, int x, int y, int z){
if(bas > y or son < x)
return;
if(bas >= x and son <= y){
yerput(k, bas, son, z);
return;
}
yerpush(k, bas, son);
yerup(sol, bas, orta, x, y, z);
yerup(sag, orta + 1, son, x, y, z);
yer[k] = yer[sol] + yer[sag];
}
int yerqu(int k, int bas, int son, int x){
if(bas == son)
return yer[k];
yerpush(k, bas, son);
if(x <= orta)
return yerqu(sol, bas, orta, x);
return yerqu(sag, orta + 1, son, x);
}
void cvpput(int k, int l){
cvp[k] += l;
cvpl[k] += l;
}
void cvppush(int k){
cvpput(sol, cvpl[k]);
cvpput(sag, cvpl[k]);
cvpl[k] = 0;
}
void cvpset(int k, int bas, int son, int x, int y){
if(bas == son){
cvp[k] = y;
return;
}
cvppush(k);
if(x <= orta)
cvpset(sol, bas, orta, x, y);
else
cvpset(sag, orta + 1, son, x, y);
cvp[k] = max(cvp[sol] , cvp[sag]);
}
void cvpup(int k, int bas, int son, int x, int y, int z){
if(bas > y or son < x)
return;
if(bas >= x and son <= y){
cvpput(k, z);
return;
}
cvppush(k);
cvpup(sol, bas, orta, x, y, z);
cvpup(sag, orta + 1, son, x, y, z);
cvp[k] = max(cvp[sol] , cvp[sag]);
}
int cvpqu(int k, int bas, int son, int x){
if(bas == son)
return cvp[k];
cvppush(k);
if(x <= orta)
return cvpqu(sol, bas, orta, x);
return cvpqu(sag, orta + 1, son, x);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
113 ms |
94456 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
113 ms |
94456 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
78 ms |
96344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
113 ms |
94456 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
