#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 yerbu(int k, int bas, int son);
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);
int yersor(int k, int bas, int son, int x, int y);
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 = 102;
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]];
a[yr] = yeni;
if(yeni == eski){
ans.pb(cvp[1]);
continue;
}
s[eski].erase(yr);
s[yeni].insert(yr);
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) );
else{
yerset(1, 1, m, eski, -1);
cvpset(1, 1, m, eski, 0);
}
if(s[yeni].size() == 1)
yerset(1, 1, m, yeni, yersor(1, 1, m, 1, yeni - 1) + 1);
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) );
else{
yerset(1, 1, m, eski, -1);
cvpset(1, 1, m, eski, 0);
}
if(s[yeni].size() == 1)
yerset(1, 1, m, yeni, yersor(1, 1, m, 1, yeni - 1) + 1);
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 yerbu(int k, int bas, int son){
if(bas == son)
yer[k] = -1;
yerbu(sol, bas, orta);
yerbu(sag, orta + 1, son);
}
void yerput(int k, int l){
yer[k] += l;
yerl[k] += l;
}
void yerpush(int k){
yerput(sol, yerl[k]);
yerput(sag, 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);
if(x <= orta)
yerset(sol, bas, orta, x, y);
else
yerset(sag, orta + 1, son, x, y);
yer[k] = max(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, z);
return;
}
yerpush(k);
yerup(sol, bas, orta, x, y, z);
yerup(sag, orta + 1, son, x, y, z);
yer[k] = max(yer[sol] , yer[sag]);
}
int yerqu(int k, int bas, int son, int x){
if(bas == son)
return yer[k];
yerpush(k);
if(x <= orta)
return yerqu(sol, bas, orta, x);
return yerqu(sag, orta + 1, son, x);
}
int yersor(int k, int bas, int son, int x, int y){
if(bas > y or son < x)
return -1;
if(bas >= x and son <= y)
return yer[k];
return max(yersor(sol, bas, orta , x, y), yersor(sag, orta + 1, son, x, y));
}
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 |
87 ms |
94420 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 |
87 ms |
94420 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 |
Correct |
61 ms |
96200 KB |
Output is correct |
| 2 |
Correct |
142 ms |
97548 KB |
Output is correct |
| 3 |
Correct |
232 ms |
98752 KB |
Output is correct |
| 4 |
Correct |
218 ms |
98808 KB |
Output is correct |
| 5 |
Correct |
206 ms |
98896 KB |
Output is correct |
| 6 |
Correct |
188 ms |
98896 KB |
Output is correct |
| 7 |
Correct |
190 ms |
98944 KB |
Output is correct |
| 8 |
Correct |
179 ms |
98944 KB |
Output is correct |
| 9 |
Correct |
164 ms |
98992 KB |
Output is correct |
| 10 |
Correct |
132 ms |
98992 KB |
Output is correct |
| 11 |
Correct |
112 ms |
99520 KB |
Output is correct |
| 12 |
Correct |
110 ms |
100228 KB |
Output is correct |
| 13 |
Correct |
140 ms |
100900 KB |
Output is correct |
| 14 |
Correct |
137 ms |
101528 KB |
Output is correct |
| 15 |
Correct |
138 ms |
102204 KB |
Output is correct |
| 16 |
Correct |
135 ms |
102832 KB |
Output is correct |
| 17 |
Correct |
142 ms |
103568 KB |
Output is correct |
| 18 |
Correct |
128 ms |
104104 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
87 ms |
94420 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
